前一章的“概率分析与随机算法”实在伤脑子，好在看过去了，现在正在看的是排序部分；

堆排序，这次说的是最大推排序（和最小堆原理也是相同的，最小堆实现），和原文中的思路也是一样的，后序有补充也会贴出来的；

最大堆...即是父节点的值大于孩子的值，若不满足条件，则经过调节使其满足条件：

维护堆：

书本中的伪码：

思想则是访问父节点，若是存在孩子节点的值大于父节点的值，则将最大的孩子节点的值与父节点进行交换，为了避免交换后的节点继续不满足条件，再次调用函数，使其满足条件，如对以下节点（不清晰部分为4）：

其中父节点3,4,5皆满足条件，到2父节点时，不满足最大堆，即进行调节：

此时则发现节点4又不满足条件了，继续调节：

调节的过程就是这样；

建堆：

我们知道，当用数组来存储n个元素的堆时，叶子节点的下标是[n / 2] + 1，[n / 2] + 2......n。如上中10个元素，6之后即为叶子节点；

这时建堆即可：

由n / 2开始向第一个元素进行建堆；

堆排序：

先构建一个最大堆，最后不断的将根节点提取出来，同时不断调节余下的节点保证是最大堆；

贴下代码：

#include 
  
   
#include 
   
     using namespace std; void MaxHeapIfy(int A[], int length, int i) //维护 { int left = i * 2; //节点i的左孩子 int right = i * 2 + 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 / 2; i >= 1; i--) { MaxHeapIfy(A, length, i); } } void HeapSort(int A[], int length) //堆排 { int temp; BuildMaxHeap(A, length); //建堆 /* cout<<"建堆情况："; // for(int i = 1; i <= length; i++) cout<