堆数据结构是一种数组对象，它可以被视为一颗完全二叉树结构。

最大堆：每个父节点都大于孩子节点。

最小堆：每个父节点都小于孩子节点。

堆排序的思想：对于给定的N个数据，初始时把这些记录看作是一颗顺序存储的二叉树，然后将其调整为一个最大堆，然后将堆的最后一个元素与堆顶元素（即二叉树的根节点）进行交换，堆的最后一个元素即为最大记录；接着将（N-1）个元素（即不包括最大记录）重新调整为一个最大堆，再将堆顶元素与堆的最后一个元素进行交换后得到次大的记录，重复该过程直到调整的堆只剩下一个元素为止，该元素即为最小记录，此时可得到一个有序序列。

堆排序主要包括两个过程：一是构建堆；二是交换堆顶元素与最后一个元素的位置。

程序如下：

#include<iostream>#include<assert.h>usingnamespacestd;voidAdjustDown(int*array,intsize,introot){assert(array);intchild=2*root+1;while(child<size){if(child+1<size&&array[child]<array[child+1]){++child;}if(array[child]>array[root]){swap(array[root],array[child]);root=child;child=2*root+1;}else{break;}}}voidHeapSort(int*array,intsize,introot){//找到第一个非叶子节点构建堆for(inti=(size-2)/2;i>=0;--i){AdjustDown(array,size,0);}for(inti=0;i<size;++i){swap(array[0],array[size-1-i]);AdjustDown(array,size-1-i,0);}}intmain(){intarray[10]={12,10,16,6,8,9,11,9,7,13};for(inti=0;i<10;++i){cout<<array[i]<<"";}cout<<endl;HeapSort(array,10,0);for(inti=0;i<10;++i){cout<<array[i]<<"";}cout<<endl;return0;}

程序运行结果：


堆排序方法对记录较少的文件效果一般，但对于记录较多的文件还是很有效的，其运行时间主要耗费在创建堆和反复调整堆上。堆排序即使在最坏的情况下，其时间复杂度也为O（N*logN）。