堆排序（最小堆）--[算法导论]

堆排序的思想在堆排序（最大堆）已做说明，故不再赘述；

总之，思想就是首先进行建堆，由于这是最小堆，故而必须保证父节点都小于孩子节点，若不满足条件，则进行调节；

最后进行堆排序，不断将最小的提取出来，并对剩下的进行调节，使之满足最小堆；

故而将最大堆中的判断父节点与孩子大小部分改变即可：

    if (left <= length && A[largest] > A[left])  //左孩子比父节点小
    {
        largest = left;
    }

    if (right <= length && A[largest] > A[right])  //右孩子最小
    {
        largest = right;
    }

这样，就将最大堆改为最小堆了...

完整代码：

#include 
  
   
#include 
   
     using namespace std; void MinHeapIfy(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; MinHeapIfy(A, length, largest); //继续维护 } } void BuildMinHeap(int A[], int length) //建堆 { for (int i = (length - 1) / 2; i >= 0; i--) { MinHeapIfy(A, length, i); } } void HeapSort(int A[], int length) //堆排 { int temp; BuildMinHeap(A, length); //建堆 cout<<"建堆情况："; // for(int i = 0; i <= length; i++) cout<