对于堆排序，首先要先知道什么是堆数据结构，堆数据结构就是一个完全二叉树，但是它有自己的性质. 例如最大堆的性质为：A[PARENT[i]]>=A[i]；即每一个结点的值大于等于其左右孩子的值，小于等于其父节点的值。我们在这里只讨论最大堆的情况。我们知道一颗完全二叉树对应一个最大堆的形式，我们要做的就是将二叉树转化为最大堆，这就是所谓的最大堆的维护，我们定义函数MaxheapFY(A,i)来进行操作。 代码：
/** *MaxheapFY(A,i):维护位置i最大堆性质，此时假设left(i)和right(i)为根的两颗二叉树都是最大堆， */void MaxheapFY(int *A,int i){//维护位置i最大堆性质，int l,r,now;l=LEFT(i);r=RIGHT(i);now=i;//记录当前结点if(l<=heapsize&&A[l]>A[now]){now=l;//交换A[l]和A[i]，并递归维护下一个当前结点now}if(r<=heapsize&&A[r]>A[now]){now=r;//交换A[l]和A[i]，并递归维护下一个当前结点now}if(now!=i){//不是当前结点，需要进行交换，用当前结点与左右孩子的最大值进行交换swap(A[i],A[now]);MaxheapFY(A,now);//递归维护当前结点，直到叶子结点}}
下面就是依据最大堆的维护性质进行建堆： /** *BuildMaxHeap(A,n):输入一个无序数组 A[1…n]，建立最大堆,我们知道数组A[(n/2+1)…n]中的元素都是 *树中的叶子结点，每一个都可以看做是一个元素的最大堆，那么我们还记得MaxheapFY(A,i)函数用来维护 *最大堆的前提是其孩子Left(i),Right(i)都是最大堆，因此我们可以利用MaxheapFY(A,i)函数，从i:[(n/2)..1] *实现最大堆的建立。 */ 代码：
void BuildMaxHeap(int *A,int n){//A[1..n]heapsize=n;//全局变量，表示最大堆的大小for(int i=n/2;i>=1;i–){//从n/2..1维护堆中每个节点的最大堆性质：结点的值大于起孩子的值MaxheapFY(A,i);}}
我们知道最大堆的第一个元素肯定是数组中最大值，我们可以交换（A[1]和A[n]）此时A[n]中已经是最大的值了，不需要在操作，只需要维护剩下的n-1个元素的下标为1的最大堆性质，运行之后就变成n-1个元素的最大堆，继续进行上面的交换操作直到剩下2个元素，就已经完成排序。 代码：
void HeapSort(int *A,int n){BuildMaxHeap(A,n);//建立最大堆for(int i=n;i>=2;i–){//cout<<A[1]<<” “;swap(A[1],A[i]);//交互A[1]和A[i],使得A[i]中为当前最大的元素heapsize–;//堆大小减去1，便于下次操作去掉已经排好序的元素MaxheapFY(A,1);//此时A[1]不一定满足最大堆的性质，重新维护下标1的最大堆的性质}}
至此我们已经完成了最大堆的建立和堆排序的代码，最大堆还有一个更重要的用处，，就是基于最大堆的最大优先队列的实现，最大优先队列就是最大元素优先，当然也有最小优先队列，是基于最小堆进行构造的。我们学过数据结构都知道，每一个数据结构都有其所为的属性和操作（方法或者是函数），我们就来看一下最大优先级队列应该支持什么样的操作呢。肯定会有：取队列的首元素，删除首元素，插入元素，修改元素关键字的值等的操作。 /** *下面给出最大优先级队列对应的操作 *1、PQueue_Insert(A,x):把元素x插入到集合S中，集合S对应的是一种最大优先级队列 *2、PQueue_Maxnum(A):返回最大优先级队列S中，键值最大的元素 *3、PQueue_Pop(A):去掉并返回最大优先级队列S最大键值的元素并删除 *4、PQueue_IncresaseKey(A,x,key):将元素x的关键字的值增加到key(尽对应这里的最大优先级队列) * *特别注意：：： *这里的优先级队列是基于最大堆建立的后，进行维护和操作的，因此在进行最大优先级队列 *操作之前，必须先进行初始胡函数PQueue_Init(A,n):初始化长度为n集合S，构造成最大堆 */ 各种函数代码实现： 初始化函数PQueue_Init(A,n)：
void PQueue_Init(int *A,int n){BuildMaxHeap(A,n);//调用建立最大堆的函数进行初始化}
返回最大元素的函数PQueue_Maxnum(A)：
int PQueue_Maxnum(int *A){return A[1];}
去掉并返回最大优先级队列的首元素PQueue_Pop(A)：
int PQueue_Pop(int *A){if(heapsize>=1){int max=A[1];A[1]=A[heapsize];–heapsize;//堆大小(最大优先级队列的大小)减去1，MaxheapFY(A,;}else return -1;//删除失败}
修改元素关键字后并维护的函数PQueue_IncresaseKey(A,x,key)：
int PQueue_IncresaseKey(int *A,int i,int key){//增大A[i]的键值if(key<A[i]) return -1;//不符合最大堆的要求（仅仅是这里的定义）A[i]=key;(i>1&&A[PARENT(i)]<A[i]){swap(A[i],A[PARENT(i)]);i=PARENT(i);//向上判断到达当前的当前的结点满足最大堆的性质或者到达祖宗结点}}
插入元素PQueue_Insert(A,x)：
void PQueu_Insert(int *A,int key){//插入首先最大优先级队列的大小增加1++heapsize;A[heapsize]=INF;//对新增的结点赋值一个永远娶不到的最小的值(仅对应于本程序的最大优先级队列)//剩下的操作就相当于将下标heapsize的关键字增大到key后，进行维护了，直接调用函数就好了PQueue_IncresaseKey(A,heapsize,key);}
至此所有函数定义并实现完成，这就是最大优先队列。
肯承认错误则错已改了一半
