第二十八节-堆

堆的定义

• 堆是一颗完全二叉树
• 堆中每个节点都必须大于等于（或者小于等于）其子树中每个节点的值。

如何实现一个堆

实现堆主要依靠堆化操作。而堆化操作又分为向上堆化和向下堆化。

就时间复杂度来说，向下堆化的操作次数少一些，所以，若是给定一个数组进行堆化，优先选择向下堆化。

若是不知道事先要存放多少个数据，需要动态建堆，那就采用向上堆化。

Java 中的 PriorityQueue 就应用了向上和向下两种堆化方式：

• 构造 PriorityQueue 时，若是直接给定一个 collection ，则对给定的 collection 进行向下堆化建堆。
• 往 PriorityQueue 中插入记录时，就把插入数据放在数组末尾，进行向上堆化。

堆排序

堆排序是一种时间复杂度为 O(nlogn) 的 原地排序 算法。堆排序的过程分为两步，先建堆，后排序。

• 建堆的操作，时间复杂度是 n。可以通过数学计算，算出建堆的时间复杂度其实是 O(n)。
• 排序：其实就是重复删除堆顶元素的过程。时间复杂度是 O(nlogn)。

所以，堆排序的总时间复杂度是 O(nlogn)。

为什么实际开发中，人们更倾向于使用快排，而不是堆排序？

快排和堆排序，都是时间复杂度 O(nlogn)，都是原地排序算法，都是不稳定的排序算法。看起来真是十分有缘分，但是，真较真起来，要排序的话，还是比较倾向于使用快排。原因如下：

• 第一点，堆排序不能友好利用 cpu 的缓存机制

快排对数据的访问，是顺序访问的，可以很好地利用 CPU 的缓存机制，在 IO 上节省大量时间。

而堆排序对数据是跳着访问的，比如对堆顶元素进行堆化，会依次访问数据下标是 1， 2， 4， 8……的数据，是对 CPU 的缓存机制不友好的。

• 第二点，对于同样的数据，在排序过程中，堆排序算法的交换次数要多于快速排序

堆排序的过程，需要经历建堆的过程，这个过程会增加数组的逆序度。假设数组原本是有序的，建堆操作后，数组反而是无序的。

这个过程，会让堆排序在排序时，比快速排序进行数据交换的次数更多。

堆的应用

虽然堆排序不如快速排序。但是特定数据结构服务特定场景。堆也有适合自己的应用场景：

• topk
• 优先级队列
• 多路归并排序
• 流里面的中位数
• 流里面的中值