1，什么是堆？ 堆就是满足一定规律的二叉树，这个规律是 ：任意父节点中的关键字>直接子节点的关键字（大头堆）或 任意父节点的关键字<直接子节点的关键字（小头堆）。 如图所示一个大头堆： 图1 大头堆示例
2，堆如何存储？ 一般采用数组（连续内存结构）来存储在内存中操作。 如上图，我们只要按图节点上的序号按数的层次排列到数组中就可以了。如下图： 图2 堆存储结构 此时，若仅知这么一个数组如何体现图1的堆逻辑关系呢？ 答案是 任何一个节点能够对应找到他的子节点位置即可。 规律： 第i个节点的左儿子是2*i+1（如图，4号位置节点元素7的左儿子是2*4+1=9，即左儿子9号位置元素1） 第i个节点的右儿子是2*i+2 3，如何保证任意给出一个数组具有堆关系呢？ 首先，得明白一个概念：堆大小。图2 数组堆存储结构之所以能满足堆，那是因为任意按照计算规律得到的儿子都比自己的值小（满足大头堆规律）。 当然，5号位置9是个叶子节点，因为计算的得到的位置11超出了堆的大小的范围（例子中的堆大小是数组的长度10，实际中，数组可以比堆要长，即不满足堆规律的数组部分不计入堆的大小），所以不存在子节点了，证明次节点是叶子。 知道堆大小，我们就可以在一段数组中维护这个堆的性质，就是把不满足堆规律的元素重新排列。 假如一个数组 1 2 3 4 指定堆大小3，我们可以得知1 2 3明显不符合堆性质1<2 , 1<3. 重新排列方法：
找出 父， 左子， 右子的最大一个如果是父最大，什么也不用干如果是某个子最大，把它和父节点交换位置如果某子不是最后的叶子，还需递归向下按1 2 3步探查很明显，1 2 3 4成堆后有3 1 2 的关系。 4，如何把数组变成堆？ 建堆的关键是依次维护堆的性质。即可以在数组上按指定堆大小size上循环维护当前堆。当然实际操作中，只要循环size/2+1次即可，如图2的位置4，堆规律已经能访问到末位置9了。 5，如何利用堆排序？ 堆的顶绝对是当前整个堆最大的元素，把它和末尾的元素交换位置后，再把堆大小缩小一个（即最大的不作为堆的元素了，可视作已经输出到排序的数组中去了），此时的堆不再满足堆性质，再按堆性质规律重新调整即可。
最后，代码描述一下整个过程：
#include <iostream> using namespace std; //打印 void printArray(int *arr ,int length){ int i = 0; for(i=0;i<length;i++){ printf("%d ",arr[i]); } } //返回堆关系 int getParent(int i){ return (i-1)/2; } int getLeft(int i){ return 2*i+1; } int getRight(int i ){ return 2*i+2; } void swap(int *a,int *b){ int temp = *a; *a = *b; *b = temp; } //8,7,9,16,14,3,2,4,10,1 //维护堆的性质 void holdMaxHeap(int *arr,int i,int heapSize){ int l_position = getLeft(i); int r_position = getRight(i); int largest = i;//默认三者之间的i位置元素值最大 if(l_position<heapSize && arr[l_position]>arr[i]){ largest = l_position; } if(r_position<heapSize && arr[r_position]>arr[largest]){ largest = r_position; } if(largest!=i){//如果父节点i的位置不是最大的 swap(arr[i],arr[largest]); //继续比较 holdMaxHeap(arr ,largest,heapSize); } } //在长度为length的数组上建立堆 void buildMaxHeap(int *arr,int length){ int heapSize = length; for(int i= heapSize/2; i>=0 ; --i){ holdMaxHeap(arr, i,heapSize); } } //堆排序 void heapSort(int * arr, int length ){ buildMaxHeap(arr,length); int heapSize = length; printArray(arr,length); while(heapSize>1){ cout<<"\n当前堆为 => ";printArray(arr,heapSize); swap(arr[0],arr[heapSize-1]); --heapSize; cout<<"\n交换输出 => ";printArray(arr,length); cout<<"\n\n调整堆"; holdMaxHeap(arr, 0 ,heapSize); } } int main(){ const int length = 10;//数组长度 int arr[] = {16,14,10,8,7,9,3,2,4,1}; heapSort(arr,length);//整个数组做堆大小来堆排序 printArray(arr,length); system("pause"); }结果：
