堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：
Key[i]=key[2i+1]Key[i]=key[2i+2]或者Key[i]=Key[2i+1]key=key[2i+2]
即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。
堆分为大顶堆和小顶堆，满足Key[i]=Key[2i+1]key=key[2i+2]称为大顶堆，满足Key[i]=key[2i+1]Key[i]=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。
怎么进行堆排序呢？
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
其基本思想为(大顶堆)：
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无须区；
2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]=R[n];
3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
操作过程如下：
1)初始化堆：将R[1..n]构造为堆；
2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。
因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。
不懂的看图，怎么一步一步来的：
具体代码：
/*堆排序(大顶堆).9.14*/#includeiostream#includealgorithmusingnamespacestd;voidHeapAdjust(int*a,inti,intsize)//调整堆{intlchild=2*i;//i的左孩子节点序号intrchild=2*i+1;//i的右孩子节点序号intmax=i;//临时变量if(i=size/2)//如果i不是叶节点就不用进行调整{if(lchild=sizea[lchild]a[max]){max=lchild;}if(rchild=sizea[rchild]a[max]){max=rchild;}if(max!=i){swap(a[i],a[max]);HeapAdjust(a,max,size);//避免调整之后以max为父节点的子树不是堆}}}voidBuildHeap(int*a,intsize)//建立堆{inti;for(i=size/2;i=1;i--)//非叶节点最大序号值为size/2{HeapAdjust(a,i,size);}}voidHeapSort(int*a,intsize)//堆排序{inti;BuildHeap(a,size);for(i=size;i=1;i--){//couta[1];swap(a[1],a[i]);//交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面//BuildHeap(a,i-1);//将余下元素重新建立为大顶堆HeapAdjust(a,1,i-1);//重新调整堆顶节点成为大顶堆}}intmain(){//inta[]={0,16,20,3,11,17,8};inta[];intsize;while(scanf(%d,size)==1size0){inti;for(i=1;i=size;i++)cina[i];HeapSort(a,size);for(i=1;i=size;i++)couta[i];coutendl;}return0;}
堆排序主要有两步,即构造初始堆和排序.AdjustDown()函数的执行时间不超过O(log2n).在排序部分,除最后一趟的堆顶元素无需再调整外,其余n-1个元素均要向下调整一次,花费时间O(log2n),故堆排序的时间复杂度为O(nlog2n).
一趟堆排序结束后,可以确定一个元素的最终位置.该排序是不稳定的排序方法.