注：堆分为最大堆和最小堆两种，下面我们讨论的堆都是指的最大堆，最小堆的性质与其是类似的。
堆数据结构是一种数组对象，可以被视为一棵完全二叉树(这棵二叉树除最后一层外，其余每层都是填满的)；我们用一个数组来存储一个堆，表示堆的数组有两个属性：length[A]表示的是数组中的元素个数，headsize[A]表示堆中元素个数(也就是说数组中的元素不一定都是堆中的元素)。 下面不加证明的给出一些堆的性质： 对于任何一个节点,其父节点为i/2(i>1)；左儿子:2*i,右儿子：2*i+1; 对于最大堆每个节点满足：A[parent[i]]>=A[i] 含n个元素堆的高度为lgn 含n个元素堆的叶子节点的编号为:n/2+1,n/2+2,……,n。
一.堆的调整函数—保持堆的性质 考虑这样一种情况，如果对于节点i，其左右子树都是一个合法的大根堆，但是节点i不满足堆的性质，那么我们可以通过调整使得以i为根节点的树满足堆的性质。那么具体的调整过程是怎样的呢？我们令largest表示A[i],A[i*2],A[2*i+1]中最大的那个，如果largest不是i那么我们就交换A[i]和A[largest]并且递归的进入到以largest为根节点的子树中继续进行调整。具体的代码实现如下：
void MaxHeadfly(int *a,int i,int HeadSize){ 其主要思想是：先是调整根节点然后递归的调整受影响的左(右)子树，直到叶子节点(a[i]<a[l]&&l<=HeadSize)largest=l;elselargest=i;if(a[largest]<a[r]&&r<=HeadSize)largest=r;if(largest!=i){///递归调整受影响的子树swp(a[i],a[largest]);MaxHeadfly(a,largest,HeadSize);}}
二.堆的建立 堆的建立其实就是一个不断调用调整函数的过程。我们知道堆的叶子节点可以看成只含有一个元素合法的大根堆，这样如果我们从第一个非叶子节点开始依次调用调整函数，就可以保证被调整的节点的左右子树都是合法的大根堆，进而可以保证调整得到的树也是合法的大根堆。具体的代码实现如下：
void BuildMaxHead(int *a,int n){ 对于叶子节点可以看成合法的单个元素的大根堆，由MaxHeadfly函数的性质可以知道 所以我们可以从编号n/2–1的节点依次调用堆的调整函数，然后就可以得到一个大根堆了。 for(int i=n/2;i>=1;i–)MaxHeadfly(a,i,n);}
三.堆排序 顾名思义堆排序就是利用堆的性质对数组进行排序，对于一个堆来说我们能利用的性质就是其根节点中的元素是最大的，，这次每次我们都可以将A[1]与A[HeadSize]进行交换，交换以后HeadSize的值减1,并且调用MaxHeadfly(a,1,HeadSize)对堆进行调整，使得A[1]又变成剩下元素中最大的，然后继续这个过程。最后得到一个有序的数组。堆排序的时间复杂度是nlgn；具体的代码实现如下：
void HeadSort(int *a,int n){此时如果我们将a[1]与a[n]互换，那么a[n]就是最大的元素了； 继续这个过程直到堆的规模减少到2，然后进行最后一次调整交换，a数组就有小到大排列了。 ///时间复杂度：建立大根堆时间O(n),每次调整时间O(lgn)共调整n-1次，所以总的复杂度nlgnBuildMaxHead(a,n); ///建立一个大根堆int HeadSize = n;for(int i=n;i>=2;i–) ///堆的规模不断减少{swp(a[1],a[i]);HeadSize–; ///交换以后就要减少堆的大小MaxHeadfly(a,1,HeadSize); ///根节点改变了,重新调整成大根堆}}
下面附上一份完整的堆排序的代码：
;int swp(int &a,int &b){int t=a;a=b;b=t;}void MaxHeadfly(int *a,int i,int HeadSize){(a[i]<a[l]&&l<=HeadSize)largest=l;elselargest=i;if(a[largest]<a[r]&&r<=HeadSize)largest=r;if(largest!=i){///递归调整受影响的子树swp(a[i],a[largest]);MaxHeadfly(a,largest,HeadSize);}}void BuildMaxHead(int *a,int n){ for(int i=n/2;i>=1;i–)MaxHeadfly(a,i,n);}void HeadSort(int *a,int n){BuildMaxHead(a,n); ///建立一个大根堆int HeadSize = n;for(int i=n;i>=2;i–) ///堆的规模不断减少{swp(a[1],a[i]);HeadSize–; ///交换以后就要减少堆的大小MaxHeadfly(a,1,HeadSize); ///根节点改变了,重新调整成大根堆}}int main(){int n=5,a[10];cout<<“请输入”<<n<<“个数：”<<endl;for(int i=1;i<=n;i++)cin>>a[i];HeadSort(a,n);cout<<“排序以后的数组：”<<endl;for(int i=1;i<=n;i++)cout<<a[i]<<” “;cout<<endl; return 0;}
四.优先队列 对于一般的队列来说，满足先进先出的性质(队尾入队，对首出队)，但对于优先队列来说，每次都是最大的/最小的元素出队。堆可以实现优先队列的基本操作，利用的也是堆的性质。优先队列一些具体的函数操作及其原理见下面的代码。
namespace std;总是最大的/最小的先出队。借助于堆的性质，我们可以///在lgn的时间内实现优选队列的任何操作void swp(int &a,int &b){int t=a;a=b;b=t;}void MaxHeadfly(int *a,int i,int HeadSize)///堆调整函数{int largest;int l=i*2,r=2*i+1;if(a[i]<a[l]&&l<=HeadSize)largest=l;elselargest=i;if(a[largest]<a[r])largest=r;if(largest!=i){swp(a[i],a[largest]);MaxHeadfly(a,largest,HeadSize);}}void BuildMaxHead(int *a,int n) ///建立一个最大堆{int k=n/2;for(int i=k;i>=1;i–)MaxHeadfly(a,i,n);}///以下为优先队列的操作int MaxNum(int *a) ///取出最大的元素{return a[1]; ///直接返回}void IncreaseKey(int *a,int x,int k){ ///将堆中编号为x的元素的值提升到k,k不能小于原来的值。///这种提升只可能会导致父节点不满足最大堆的性质，所以直接向上递归的检查a[x]=k;while(x>1&&a[x/2]<a[x]){swp(a[x],a[x/2]);x=x/2;}}int ExtractMax(int *a,int &HeadSize){ 然后再将HeadSize的值减1(相当于去掉一个叶子节点)；然后再调用///MaxHeadfly(a,1,HeadSize)对堆进行调整，保证堆的性质。swp(a[1],a[HeadSize]);HeadSize–;MaxHeadfly(a,1,HeadSize);return a[HeadSize];}void Insert(int *a,int &HeadSize,int x){ 然后再调用上面的调整函数将该叶子节点的值调整为xHeadSize++; ///增加一个叶子节点a[HeadSize]=-1*INF;IncreaseKey(a,HeadSize,x);}int main(){int a[10];int n=5;cout<<“请输入5个数: “<<endl;for(int i=1;i<=n;i++)cin>>a[i];int HeadSize=n;BuildMaxHead(a,n);///取出队列中 最大的那个元素cout<<“最大的元素是: “<<MaxNum(a)<<endl;ExtractMax(a,HeadSize);cout<<“移除最大元素后，剩下元素中最大的是: “<<MaxNum(a)<<endl;///将第4个元素增加到100IncreaseKey(a,4,100);cout<<“将第4个元素增加到100后,最大元素是: “<<MaxNum(a)<<endl;///将110插入到队列中Insert(a,HeadSize,110);cout<<“插入110后，最大元素是: “<<MaxNum(a)<<endl; return 0;}
值不值得，真是不足为外人道，自己心里有数就行。
