堆排序（最大堆进阶）--[算法导论]

上篇【堆排序（最大堆）】说过，代码是按照书中的伪码写出，书中的根结点是1，但一般我们数组的下标由0开始，故而现在改为由0开始；

上篇已说过实现的过程，故而不再赘述，细节可见上篇；

将其中的一些条件改变即可：

首先是建堆的值，由0开始的根结点，对于A[n]，它的父节点是(n - 1) / 2，并且到0为止，都是父节点；

故而建堆：

    for (int i = (length - 1) / 2; i >= 0; i--)
    {
        MaxHeapIfy(A, length, i);
    }

另外在节点的两个孩子则为：

    int left = i * 2 + 1;  //节点i的左孩子
    int right = left + 1; //节点i的右孩子节点

在进行堆排时，因为A[0]是第一个元素，故而：

    for(int i = length; i >= 1;)  //最后一个肯定是最小的
    {
        temp = A[i];    //交换堆的第一个元素和堆的最后一个元素
        A[i] = A[0];
        A[0] = temp;
        i--;        //堆的大小减一
        MaxHeapIfy(A, i, 0);  //调堆
    }

好的，贴出代码：

#include 
  
   
#include 
   
     using namespace std; void MaxHeapIfy(int A[], int length, int i) //维护 { int left = i * 2 + 1; //节点i的左孩子 int right = left + 1; //节点i的右孩子节点 int largest = i; //默认父节点 if (left <= length && A[largest] < A[left]) //左孩子比父节点大 { largest = left; } if (right <= length && A[largest] < A[right]) //右孩子最大 { largest = right; } if (i != largest) //最大值不是父节点 { int temp = A[largest]; //exchange A[largest] = A[i]; A[i] = temp; MaxHeapIfy(A, length, largest); //继续维护 } } void BuildMaxHeap(int A[], int length) //建堆 { for (int i = (length - 1) / 2; i >= 0; i--) { MaxHeapIfy(A, length, i); } } void HeapSort(int A[], int length) //堆排 { int temp; BuildMaxHeap(A, length); //建堆 cout<<"建堆情况："; // for(int i = 0; i <= length; i++) cout<