【问题描述】：关于排序的问题，我们之前见过冒泡排序，其时间复杂度为O(N^2)，效率很低，那有没有高效一点的排序方法？我们就要说到堆排序了，本博客中主要讨论堆排序的实现，以及其时间复杂度分析。
【解题思路】：我们知道如果一个二叉树满足堆的特性，那么堆顶元素则一定是整个堆中最大或最小的元素（这取决于大堆或小堆），那如果我们需要将一组数据进行升序排序，那么我们将这组元素拿来创建一个大堆，堆顶元素为整个数组中最大元素。然后利用堆删除的思想，将堆中最后一个节点的元素与堆顶元素进行交换，现在我们就将这个最大的元素放到了最后一个节点的位置上，接下来将新置换过去的堆顶元素调整至合适位置，再将堆中有效节点个数减一，现在堆顶元素就是整个数组中次大的那个了，同理进行接下来的步骤，最终我们就会得到一个按升序排好序的堆了。
接下来以升序排序为例，来看一下具体的代码实现：
堆调整（大堆）：
void Swap(HPDatatype* pLeft, HPDatatype* pRight) { HPDatatype tmp = *pLeft; *pLeft = *pRight; *pRight = tmp; } void HeapAdjust(int* array, int size, int parent) { int child = parent * 2 + 1; while (child < size) { if (child + 1 < size&&array[child + 1] > array[child]) child += 1; if (array[parent] < array[child]) { Swap(&array[parent], &array[child]); parent = child; child = parent * 2 + 1; } } }堆排序：
void HeapSort(int* array, int size) { //大堆--->升序 //小堆--->降序 int root = ((size - 2) >> 1);//找倒数第一个非叶节点 for (; root >= 0; --root) HeapAdjust(array, size, root); //排序，采用堆删除的思想 int end = size - 1; while (end) { Swap(&array[end], &array[0]); HeapAdjust(array, end, 0); end--; } }如果是要降序排序的话，则在堆调整时取小的节点。
时间复杂度分析：
先看一下创建堆的时间复杂度：
需要调整的节点个数：N/2个。根据二叉树的性质我们可知终端节点数n0=度为2节点数n2+1，将常数1忽略掉可得：n0=n2。所有的n2都需要调整，所以需要调整的节点个数为总节点数N/2。
调整一次的时间复杂度：logN。完全二叉树共有N个节点，高度为log(N+1)，化简到logN，调整一次的时间复杂度最差情况需要调整二叉树的高度次，所以调整一次的时间复杂度为logN。
所以创建堆的时间复杂度为：N/2logN，化简到NlogN。
然后再来看一下排序时的时间复杂度：排序时我们采用的是删除堆的思想，而删除堆的时间复杂度也是NlogN。
所以堆排序的时间复杂度为：2NlogN，化简到NlogN。
