什么是堆排序？有哪些典型应用？

在上一篇文章中，我们解释了二叉堆。现在的堆排序算法主要依赖于二叉堆。如果你不知道什么是二叉堆，可以看一下：

【算法与数据结构】什么是二叉堆？

使用辅助数组实现堆排序算法

如果给你一个二叉堆，根据二叉堆的特点，你会如何利用二叉堆来实现堆排序呢？

我们都知道二叉堆有一个非常特殊的节点——堆顶。堆顶要么是所有节点中最大的元素，要么是最小的元素。这主要取决于二叉堆是最小堆还是最大堆。

今天我们暂时选择以最小堆为例。

根据堆顶的特点，我们就可以实现我们的堆排序了。

让我们看一下下面的例子：

对于具有10 个节点元素的二叉堆，如下所示：

我们删除堆顶的节点，然后将删除的节点放到一个辅助数组help中。

显然，被删除的节点是堆中最小的节点。接下来我们继续删除二叉堆的顶部，然后将删除的元素存储到help数组中。

显然，第二次删除的节点是原二叉堆中第二小的节点。

继续删除

继续连续删除堆顶6次，将删除的节点一次一个放入help数组中。

二叉堆中只剩下最后一个节点了。该节点也是原二叉堆中最大的节点。该节点被删除或放入帮助数组中。

此时，二叉堆的所有元素都已被删除。看一下帮助数组。这是一个有序数组。事实上，通过从二叉堆的顶部逐一取出最小值，并将其存储到另一个辅助数组中，当二叉堆耗尽时，我们就完成了一次堆排序。

其实不需要辅助数组

在上面的堆排序过程中，我们使用了辅助数组的帮助。但事实上，我们真的需要辅助数组吗？

我们在上一篇文章讲二进制堆的时候也讲过。二叉堆实现时，是以数组的形式存储的。

要从二叉堆中删除一个元素，为了充分利用空间，我们实际上可以将删除的元素直接存储在二叉堆的最后一个元素中。例如：

删除堆顶，并将删除的元素作为最后一个元素。

继续删除，将删除的元素放到最后第二个位置

继续删除，将删除的元素放在最后第三个位置

等等…。

这样，对于一个包含n个元素的二叉堆，经过n-1次（不需要删除n次）删除后，数组就变成了有序数组。

那么，给你一个无序数组，我们需要将这个数组构造成一个二叉堆，然后通过将堆顶一一删除来实现堆排序。

事实上，它并没有被删除。相当于将堆顶的元素与堆尾交换，然后通过下沉将二叉树恢复为二叉堆。

代码如下：

public class HeapSort { /** * 下沉操作，执行删除操作相当于将最后一个* * 元素赋值给根元素，然后对根元素执行下沉操作* @param arr * @paramparent 到的元素下沉下标* @param length array length*/public static int[] downAdjust(int[] arr, intparent, int length) { //暂时保证下沉元素int temp=arr[parent]; //定位左子节点位置int child=2 * Parent + 1; //开始下沉while (child length) { //如果右子节点小于左子节点，则定位右子节点if (child + 1 length arr[child] arr [child + 1]) { child++; } //如果父节点小于等于子节点，则下沉结束if (temp=arr[child]) break; //单向赋值arr[parent]=arr[child ];父=子；子级=2 * 父级+ 1； } arr[父]=临时；返回arr； } //堆排序public static int[] heapSort(int[] arr, int length) { //构建2个分叉堆for (int i=(length - 2)/2; i=0; i--) { arr=downAdjust(arr, i, 长度); } //进行堆排序for (int i=length - 1; i=1; i--) { //将堆顶元素与最后一个元素交换int temp=arr[i]; arr[i]=arr[0]; arr[0]=温度； //接收器调整arr=downAdjust(arr, 0, i);返回arr； } //测试public static void main(String[] args) { int[] arr=new int[]{1, 3, 5,2, 0 ,10,6}; System.out.println(Arrays.toString(arr)); arr=heapSort(arr, arr.length); System.out.println(Arrays.toString(arr)); }}对于堆我直接给出了时间复杂度。有兴趣的可以自己推理一下。这并不难。堆的时间复杂度是O(nlogn)。空间复杂度为O(1)。

这里你可能会问，堆排序的时间复杂度是O(nlogn)，和快速排序一样，归并排序的时间复杂度也是O(nlogn)，那么使用时应该如何选择呢？

这里解释一下：快速排序的平均复杂度是O(logn)。事实上，快速排序最坏的时间复杂度是O(n^2.)，而归并排序和堆排序都稳定在O(nlogn)。

我给你一个问题，比如我给你一个有n个元素的无序数组，让你找出第k大的数。那么你会选择哪种排序呢？

显然在这个问题中，堆排序是最好的。我们不需要对整个数组进行排序，我们只需要对前k 个数字进行排序。至于代码怎么实现，我就不给你们代码了。你可以尝试一下。