堆排序就是利用堆这种数据结构进行排序的算法，堆排序属于选择排序。
堆是一棵顺序存储的完全二叉树
堆排序的时间复杂度： O(nlogn)，属于不稳定排序。
堆排序就是利用堆得性质堆数组进行排序，待排序元素存放在一个数组Arr[0 ……n] 中，将Arr用一颗完全二叉树来表示，数组第一个元素就是完全二叉树的根，后面依次按层从左至右为，左孩子，右孩子，任意节点Arr[ i ] 的左孩子是Arr[ 2i+1 ]，右孩子是 Arr[ 2i+2 ]，对这个二叉树进行调整，使各个节点满足：
Arr[ i ].key >= Arr[ 2i ].key && Arr[ i ].key >= Arr[ 2i+1 ].key
(其中 i = 1, 2, 3,……, [n/2] ）
设有一个无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。
1、构造初始堆
2、构造初始堆后，就需要完整的堆排序
到此，就构造了有序的堆
代码实现首先给出完整部分的堆排序代码思路，主要分为两步，第一：建一个大堆，第二：交换根节点和最后一个叶子交换，再根据堆性质，调整堆，也就是第一步所做的工作，堆长度 -1 。
//堆排序void HeapSort(int A[], int N){int i;//步骤一：根据A数组元素，创建大根堆//从第 n/2 个记录开始进行建堆for (i = N / 2; i >= 0; i--){PercDown(A, i, N);}//步骤二：调整大根堆for (i = N - 1; i > 0; i--){//首尾交换Swap(&A[0], &A[i]);//将最后一个叶子节点与根节点进行交换，//再根据堆性质进行调整PercDown(A, 0, i);}}交换根节点和最后一个叶子结点的操作。在传递参数中，其实已经将根和最后一个叶子节点下标传了进来（0和i），所以直接交换元素就可以了。
//交换两个元素的位置//为什么传指针，就不啰嗦了void Swap(int *num1, int *num2){int tmp = *num1;*num1 = *num2;*num2 = tmp;}调整部分是堆排序的重点，也是难点。调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。
//给定父节点的索引，得到左子节点的索引,跟的索引为0#define LeftChild(i) (2*(i)+1)//元素向下调整方法void PercDown(int A[], int i, int N){//子节点的索引号int child;//存储当前父节点元素的临时变量//(注：每一个节点都可以看作是其子树的根节点)int tmp;for (tmp = A[i]; LeftChild(i)<N; i = child){child = LeftChild(i); //左子节点索引//挑选出左、右子节点中较大者if (child != N - 1 && A[child + 1] > A[child]){child++;}//比较当前父节点与较大子节点if (A[i]<A[child]){//交换当前父节点处的元素值与较大子节点的元素值//此处也可以调用：Swap(A[i], A[child])tmp = A[i];A[i] = A[child];A[child] = tmp;}else{break;}}} 时间复杂度及总结1、堆排序最大的优点就是，在最坏的情况下，时间复杂度仍为 O(n*logn)；
2、堆排序只需要存放一个记录的辅助空间，所以堆排序也称原地排序；
3、堆排序是不稳定的；
4、不适用于待排序数n较小的情况，但对n较大的文件还是很有效的；
4、堆排序可以通过树形结构保存部分比较结果，减少比较次数。