数据结构与算法C#版笔记--排序(Sort)-中-堆排序(HeapSort)

时间：2010-12-21 来源：菩提树下的杨过

上图就是一颗完全二叉树，如果每个节点按从上到下，从左至右标上序号，则可以用数组来实现顺性存储，同时其序号：

1、如果i>1，则序号为i的父结节序号为i/2(这里/指整除) 言外之意：整个数组前一半都是父节点，后一半则是叶节点

2、如果2*i<=n（这里n为整颗树的节点总数），则序号为i的左子节点序号为2*i

3、如果2*i +1 <=n，则序号为i的右子节点序号为2*i + 1

好了，再来看看"堆(Heap)"是个神马玩意儿？

其实，堆就是一颗完全二叉树，由上面的知识点回顾可以知道，任意给定一个数组，我们就能将它构造成一颗完全二叉树，也就是创建一个“堆”--ps：还好业内标准没把它称为一坨：）

其中，堆又可以分为最大堆与最小堆，下图就是一个最大堆：

简言之：每个(父)节点的值，都比其子节点值大，这样的堆就称为最大堆；反过来类推，如果每个（父）节点的值，都比其子节点小，就叫最小堆。

下面该"堆排序"(HeapSort)登场了，其思路为：

1、先将给定待排序的数组通过一定处理，形成一个“最大堆”

2、然后将根节点(root)与最后一个序号的节点(lastNode)对换，这样值最大的根节点，就“沉”到所有节点最后了(也就是垫底了)，下轮处理就不用理会它了.

3、因为第2步的操作，剩下的节点肯定已经不满足最大堆的定义了(因为把小值的末节点换成根节点了，它的子节点中肯定会有值比它大的)，然后再类似第1步的处理，把这些剩下的节点重新排成“最大堆”

4、重复第2步的操作，将“新最大堆的根节点”与“新最大堆的末结点”(其实就是整个数组的倒数第二个节点，因为在第一轮处理中，最大值的节点已经沉到最后了，所以新最大堆的最末节点就是整个数组的倒数第二个节点)对换，这样第二大的元素也沉到适当的位置了，以后就不用理它了，然后继续把剩下的节点，重组成最大堆

5、反复以上过程，直到最后剩下的节点只剩一个为止（即没办法再继续重组成最大堆），这时排序结束，最后剩下的节点，肯定就是值最小的

假设给定数组new int[] {1,3,5,6,4,2}，要求用“堆排序算法”从小到大排序，上面的算法描述图解为：

理解以上思路后，堆排序就拆分成了二个问题：

A、如何将数组指定范围的N个元素创建一个"最大堆"？

B、如何用一定的算法，反复调用A中的"最大堆创建"方法，以处理剩下的节点，直到最终只剩一个元素为止

创建最大堆的算法，完全依赖于完全二叉树的数学特性，代码如下：

        /// <summary>
        /// 创建最大堆
        /// </summary>
        /// <param name="arr">待处理的数组</param>
        /// <param name="low">指定连续待处理元素范围的下标下限</param>
        /// <param name="high">指定连续待处理元素范围的下标上限</param>
        static void CreateMaxHeap(int[] arr, int low, int high)
        {
            if ((low < high) && (high <= arr.Length - 1))
            {
                int j = 0, k = 0, t = 0;             

                //根据完全二叉树特性，前一半元素都是父节点，所以只需要遍历前一半即可
                for (int i = high / 2; i >= low; --i)
                {
                    k = i;
                    t = arr[i];//暂存当前节点值
                    j = 2 * i + 1;//计算左节点下标(注意：数组下标是从0开始的，而完全二叉树的序号是从1开始的，所以这里的2*i+1是左子节点，而非右子节点！)                    
                    while (j <= high) //如果左节点存在
                    {
                        //如果右节点也存在，且右节点更大
                        if ((j < high) && (j + 1 <= high) && (arr[j] < arr[j + 1]))
                        {
                            ++j;//将j值调整到右节点的序号，即经过该if判断后，j对应的元素就是i元素的左、右子节点中值最大的
                        }

                        //如果本身节点比子节点小
                        if (t < arr[j])
                        {
                            arr[k] = arr[j];//将自己节点的值，更新为左右子节点中最大的值
                            k = j;//然后保存左右子节点中最大元素的下标(因为实际上要做的是将最大子节点与自身进行值交换，上一步只完成了交换值的一部分，后面还会继续处理才能完成整个交换)
                            j = 2 * k + 1;//交换后，j元素就是父节点了，然后重新以j元素为父节点，继续考量其"左子节点"，准备进入新一轮while循环
                        }
                        else //如果本身已经是最大值了，则说明元素i所对应的子树，已经是最大堆，则直接跳出循环
                        {                            
                            break;
                        }
                    }
                    arr[k] = t;//接上面的交换值操作，将最大子节点的元素值替换为t(因为最近的一次if语句中，k=j 了，所以这里的arr[k]其实就是arr[j]=t，即完成了值交换的最后一步，当然如果最近一次的if语句为false,根本没进入，则这时的k仍然是i，维持原值而已)
                }
            }
        }

反复调用该算法排序的代码：

        static void HeapSort(int[] arr)
        {
            int tmp = 0;
            //初始时，将整个数组排列成"初始最大堆"
            CreateMaxHeap(arr, 0, arr.Length-1);
            for (int i = arr.Length - 1; i > 0; --i)
            {
                //将根节点与最末结点对换
                tmp = arr[0];
                arr[0] = arr[i];
                arr[i] = tmp;
                //去掉沉底的元素，剩下的元素重新排列成“最大堆”
                CreateMaxHeap(arr, 0, i - 1);
            }
        }