深入解析堆排序的算法思想，轻松弄懂复杂算法，附源码！

1.什么是堆？

堆是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

1.堆中某个节点的值总是不大于或不小于其父节点的值；

2.堆总是一棵完全二叉树。

如果有想学习java的同学，可来我们的java技术学习QQ群：165080868，免费送整套系统的java视频教程！我每晚上8点还会在群内直播讲解Java知识，欢迎大家前来学习哦。下面是部分资料截图：

2.什么是堆排序？

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

3.算法思想

最大堆的算法思想是：

先将初始的R[0…n-1]建立成最大堆，此时是无序堆，而堆顶是最大元素

再将堆顶R[0]和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0…n-2]和有序区R[n-1]，且满足R[0…n-2].keys ≤ R[n-1].key

由于交换后，前R[0…n-2]可能不满足最大堆的性质，因此再调整前R[0…n-2]为最大堆，直到只有R[0]最后一个元素才调整完成。

最大堆排序完成后，其实是升序序列，每次调整堆都是要得到最大的一个元素，然后与当前堆的最后一个元素交换，因此最后所得到的序列是升序序列。

最小堆的算法思想是：

先将初始的R[0…n-1]建立成最小堆，此时是无序堆，而堆顶元素是最小的元素

再将堆顶R[0]与无序区的最后一个R[n-1]交换，由此得到新的无序堆R[0…n-2]和有序堆R[n-1]，且满足R[0…n-2].keys >= R[n-1].key

由于交换后，前R[0…n-2]可能不满足最小堆的性质，因此再调整前R[0…n-2]为最小堆，直到只有R[0]最后一个元素才调整完成

最小堆排序完成后，其实是降序序列，每次调整堆都是要得到最小的一个元素，然后与当前无序堆的最后一个元素交换，所以所得到的序列是降序的。

提示：堆排序的过程，其实就是不断地扩大有序区，然后不断地缩小无序区，直到只有有序区的过程。

4.排序过程分析

因为算法比较抽象，这里直接通过举个小例子来说明堆排序的过程是如何的。下面我们用这个无序序列采用最大堆的进行堆排序，所得到的序列就是升序序列（ASC）。

无序序列：89,-7,999,-89,7,0,-888,7,-7

第一步：初始化建成最大堆：

第二步：将堆顶最大元素999与无序区的最后一个元素交换，使999成为有序区。交换后，-7成为堆顶，由于-7并不是无序区中最大的元素，因此需要调整无序区，使无序区中最大值89成为堆顶，所以-7与89交换。交换后导致89的右子树不满足最大堆的性质，因此要对右子树调整成最大堆，所以-7要与0交换，如下图：

从图中看到，当-7成89交换后，堆顶是最大元素了，但是-7的左孩子是0，右孩子是-888，由于-7<0，导致-7这个结点不满足堆的性质，因此需要调整它。所以，0与-7交换。

然后不断重复着第二步的过程，直到全部成为有序区。

最后：所得到的是升序序列

5.时间复杂度

堆排序的时间，主要由建立初始堆和反复调整堆这两部分的时间开销构成.由于堆排序是不稳定的，它得扭到的时间复杂度会根据实际情况较大，因此只能取平均时间复杂度。

平均时间复杂度为：O( N * log2(N) )

堆排序耗时的操作有：初始堆 + 反复调整堆，时间复杂度如下：

1.初始建堆：每个父节点会和左右子节点进行最多2次比较和1次交换，所以复杂度跟父节点个数有关。根据2x <= n（x为n个元素可以折半的次数，也就是父节点个数），得出x = log2n。即O ( log2n )

2.反复调整堆：由于初始化堆过程中，会记录数组比较结果，所以堆排序对原序列的数组顺序并不敏感，最好情况和最坏情况差不多。需要抽取 n-1 次堆顶元素，每次取堆顶元素都需要重建堆（O(重建堆) < O(初始堆)）。所以小于 O(n-1) * O(log2n)

使用建议：

由于初始化堆需要比较的次数较多，因此，堆排序比较适合于数据量非常大的场合（百万数据或更多）。由于高效的快速排序是基于递归实现的，所以在数据量非常大时会发生堆栈溢出错误。

6.Java示例代码

欢迎关注胖胖爱Java的简书号，可视化学习java，每天更新文章，让Java学习更加简单。

声明：本文内容来源于网络，如有侵权请联系删除