数据结构--堆排序（超详细！）
一、前言
堆排序与Top K问题是堆的两大应用，在我们日常也有很广泛的用处
我们已经上面已经说过了堆，这次来说堆的其中一个应用---堆排序。
二、堆排序
堆排序优势在哪里？有什么恐怖之处吗？
重点：拿一个举例：我们上一篇博客在代码运用过程中，我们的HeapPop函数每次删除堆顶元素之后进行向下调整之后，都能找到次大或者次小的值。
int main()
{HP php;InitHeap(&php);int a[] = { 4,7,2,3,9,5,1 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)//建堆{PushHeap(&php, a[i]);}while (!HeapEmpty(&php))//进入循环，直至堆为空{printf("%d ", HeapTop(&php));//打印堆顶元素HeapPop(&php);//删除堆顶元素}DestroyHeap(&php);return 0;
}
这样就把我们所想要的排序好了，我们每取出一个次大或者次小的值，时间复杂度都是O(log N)，当有1000个数据时，各个元素比较查找那就需要进行1000次，而我们这种做法10次就够了。效率很高。分析上面代码，还是有点缺陷的，在我们建堆的时候，我们是从源头数组里面取数据，再新开辟空间建堆，源头数组并没有变化，这便造成了空间的浪费。所以，有没有一种高效又节省空间的方法呢----堆排序。
我们要想节省空间，最好需要做到不另开辟空间，我们已经定义了一个数组，并且想将数组里面的元素进行排序，那为什么我们不在原数组上找路子呢？
1、建堆
开辟空间的建堆方式，先将源头数组里面的元素放入我们开辟的结构体中的数组里，再进行向上调整建堆。那为何我们不直接将源头数组元素直接进行向上调整呢？
我们可以直接将原数组传给AdjustUp函数，再先将数组中第一个元素进行向上调整，接着再第二个元素，这样依次进行向上调整。
int a[] = { 4,7,2,3,9,5,1,6,8};int n = sizeof(a) / sizeof(a[0]);int i = 0;for (i = 1; i < n; i++){AdjustUp(&a, i);}我们打印一下看看结果：
因为我们上述向上调整函数最终调整为小堆，这里就拿小堆来做参考：
监视查看数组的变化：
可以看到，数组中元素已经是小堆。这样既满足了我们的建堆要求，也降低了空间的消耗
2、排序
那么，话说回来，堆是随便建的吗？直接建一个大堆或者小堆都可以满足我们要求吗？有没有什么要求呢？
我们在开头举国一个例子：我们的HeapPop函数每次删除堆顶元素之后进行向下调整之后，都能找到次大或者次小的值。
HeapPop函数的逻辑是，将堆顶元素A与堆尾元素B互换，然后A删除，将B向下调整建堆。
如果刚开始建的是小堆，我们交换堆顶元素A和队尾元素B后不着急删除A，既然是小堆，那么A肯定是所有元素中的最小值，交换后在队尾。我们再进行向下调整后，重建建小堆(这里重新建堆时不要将A也加入建堆的操作中，因为我们没有删除A)，这时候的堆顶元素就是次小的值。我们将堆顶元素再与倒数第二个元素进行交换，这样次小的值就在倒数第二个位置了，再进行向下调整。这两个操作多次进行，直到剩下最后一个元素。我们每次都是找次小的值将它放在数组中最后一个，这样下来，我们最终就会得到排序好的元素，为降序。
如果是大堆呢？每次向下调整都会找到次大的值，堆顶元素与堆尾元素交换后，次大的值依次从后向前排列，最后我们便得到排序好的元素，为升序。
所以我们可以总结出，升序建大堆，降序建小堆。
代码如下(以降序举例)：
int main()
{int a[] = { 4,7,2,3,9,5,1,6,8};int n = sizeof(a) / sizeof(a[0]);int i = 0;//在数组里建堆，减少了空间消耗//升序建大堆，降序建小堆 for (i = 1; i < n; i++){AdjustUp(&a, i);}//查看建堆后的元素排列for (i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");//重新定义一个变量，将元素大小赋值给它.不改变nint end = n - 1;while(end > 0){Swap_HP(&a[0],&a[end]);//交换堆顶元素与堆尾元素AdjustDown(&a,end, 0);//向下调整找到此小值end--;//在下一次交换中，让新的堆顶元素与新的堆尾元素交换。}for (i = 0; i < n; i++){ printf("%d ", a[i]);}return 0;
}这一趟下来时间复杂度只有N*logN，比最开始学的冒泡排序快了不少。数据越多，就越能体现出堆排序的优越性！
以上就是堆排序要说的所有内容。