6. 堆排序

基本思想：堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最小（大）堆，依次类推，最终得到排序的序列。

堆排序分为大顶堆和小顶堆排序。大顶堆：堆对应一棵完全二叉树，且所有非叶结点的值均不小于其子女的值，根结点（堆顶元素）的值是最大的。而小顶堆正好相反，小顶堆：堆对应一棵完全二叉树，且所有非叶结点的值均不大于其子女的值，根结点（堆顶元素）的值是最小的。

举个例子：

(a)大顶堆序列：（96, 83,27,38,11,09)

(b)小顶堆序列：（12，36，24，85，47，30，53，91）

实现堆排序需解决两个问题：

　　1. 如何将n 个待排序的数建成堆?

　　2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆?

首先讨论第二个问题：输出堆顶元素后，怎样对剩余n-1元素重新建成堆？

调整小顶堆的方法：

　　1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。

　　2）将根结点与左、右子树中较小元素的进行交换。

　　3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.

　　4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.

　　5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

　　称这个自根结点到叶子结点的调整过程为筛选。如图：

再讨论第一个问题，如何将n 个待排序元素初始建堆？

　　建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

　　1）n 个结点的完全二叉树，则最后一个结点是第n/2个结点的子树。

　　2）筛选从第n/2个结点为根的子树开始，该子树成为堆。

　　3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

　　如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）

​

C#算法实现：

/// <summary>        /// 堆排序        /// 堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的        /// 每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最小堆，依次类推，最终得到排序的序列。        /// </summary>        /// <param name="arr"></param>        /// <param name="length"></param>        private static void HeapSort(int[] arr, int length)        {            CreateHeap(arr, length);            //从最后的节点进行调整            for (int i = length - 1; i > 0; i--)            {                //交换堆顶和最后一个节点的元素                Swap(ref arr[0], ref arr[i]);                //每次交换进行调整                AdjustHeap(arr, 0, i - 1);            }        }        /// <summary>        /// 建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。        /// 1）n 个结点的完全二叉树，则最后一个结点是第n/2个结点的子树。        /// 2）筛选从第n/2个结点为根的子树开始，该子树成为堆。        /// 3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。        /// 完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。        /// </summary>        private static void CreateHeap(int[] arr, int length)        {            for (int i = length / 2 - 1; i >= 0; i--)            {                AdjustHeap(arr, i, length - 1);            }        }        private static void AdjustHeap(int[] arr, int start, int length)        {            int root = start;            int child = root * 2 + 1;            while (child <= length)            {                //若子节点指标在范围内才做比较                if (child + 1 <= length && arr[child] < arr[child + 1])                {                    //先比较两个子节点大小，选择最大的                    child++;                }                //如果父节点大於子节点代表调整完毕，直接跳出函数                if (arr[root] > arr[child])                {                    return;                }                else                {                     //否则交换父子内容再继续子节点和孙节点比较                    Swap(ref arr[root], ref arr[child]);                    root = child;                    child = root * 2 + 1;                }            }        }

堆排序，还有一个扩展知识，二叉堆，对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。更多实现：C#数据结构-二叉堆实现