堆排序应用

优先级队列，顾名思义，它首先应该是一个队列。

队列最大的特性就是先进先出。不过，在优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队。

一个堆就可以看作一个优先级队列。很多时候，它们只是概念上的区分而已。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。

假设我们有100个小文件，每个文件的大小是100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。

我们将从小文件中取出来的字符串放入到小顶堆中，那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。我们将这个字符串放入到大文件中，并将其从堆中删除。然后再从小文件中取出下一个字符串，放入到堆中。循环这个过程，就可以将100个小文件中的数据依次放入到大文件中。

这种求 Top K 的问题抽象成两类。一类是针对静态数据集合，也就是说数据集合事先确定，不会再变。另一类是针对动态数据集合，也就是说数据集合事先并不确定，有数据动态地加入到集合中。

维护一个大小为K的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。

遍历数组需要O(n)的时间复杂度，一次堆化 *** 作需要O(logK)的时间复杂度，所以最坏情况下，n 个元素都入堆一次，时间复杂度就是 O(nlogK)。

维护一个 K 大小的小顶堆，当有数据被添加到集合中时，我们就拿它与堆顶的元素对比。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理。这样，无论任何时候需要查询当前的前 K 大数据，我们都可以立刻返回给他。

对于一组静态数据，中位数是固定的，我们可以先排序，第n/2个数据就是中位数。每次询问中位数的时候，我们直接返回这个固定的值就好了。所以，尽管排序的代价比较大，但是边际成本会很小。

我们需要维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。

在如上插入和删除堆顶元素的 *** 作中，主要的时间消耗都在堆化这个过程中，堆化 *** 作需要比较和交换的次数最大不会超过树的高度，而前面我们说过，完全二叉树的高度是2的对数，因此插入和删除堆顶元素 *** 作的时间复杂度是O(logn)。

给定一个数组，其中的元素都是无序杂乱的，我们怎么对它进行堆排序呢？

首先，我们需要将该数组建立为一个大顶堆（小顶堆），通常有以下两种建堆的方法：

经过上一步的建堆 *** 作，我们得到了一个大顶堆，但是数组中的数据看上去仍然是无序的，我们需要基于这个大顶堆把数组排下序。

首先从堆顶取出元素，这个元素肯定是最大的，把它和数组最后一个元素进行交换，放到位置n，然后堆中剩下的元素不断地进行堆化，并始终取堆顶元素依次放到n-1,n-2,n-3的位置上，当堆中只剩最后一个元素的时候，此时数组就是一个有序数列了。

堆排序的过程中，我们需要对n个元素进行堆化 *** 作，每次堆化 *** 作时间复杂度取决于完全二叉树的高度，所以最终得到堆排序的时间复杂度为O(nlogn)。

堆排序不需要借助很多的额外存储空间，因此它属于原地排序；

堆排序过程中会可能改变相同值的位置，所以不是稳定的排序算法；

虽然堆排序和快速排序时间的时间复杂度都是O(nlogn)，但通常都认为堆排序的性能是比不上快速排序的。

如上已经讲解过了。

优先级队列中，数据的出队不是按照入队先后来决定的，而是按照优先级来的，优先级高（低）的就先出队，实现优先级队列的方法有很多，但是其中使用堆来实现是最为快捷高效的。比如Java中的PriorityQueue。

场景一：合并有序小文件

假设我们有n个小文件，每个大小为100MB，每个文件中存放的都是有序的字符串，我们如何把这n个小文件中的字符串有序地全都合并到一个大文件中呢？

这里有两个方法：

我们可以看到，这两种方法的区别在于，前者需要每次遍历数组找到最小值，后者则是有删除和插入两个堆化的过程。堆化过程的时间复杂度为O(logn)，明显比遍历数组的O(n)要好，所以方法二更加高效。

场景二：实现高性能定时器

假设我们使用定时器设置了很多个待执行的任务，那么如何实现定时触发这些提前设定好的任务呢？

这里说三个方法：

方法2和方法3其实是类似的，关键在于采取什么样的数据结构和算法来获取最小值。如果存在中途插入或者取消任务的情况，对于方法2来说，插入一个元素到有序列表中和从有序列表中删除一个给定元素时间复杂度是多少呢？假设我们采用效率最高的二分查找，那么是O(logn)，但是插入和删除元素是要搬移元素的，这个时间是O(n)，所以总的下来就是O(n)；如果使用方法3，那么无论插入还是删除元素，都是一个堆化的过程，时间复杂度为O(logn)，所以方法3中使用堆更加高效。

假设存量数据量为n，我们需要从n中找到Top-k的元素，并且针对不断添加进来的数据，我们都要获取最新的Top-k元素，这种问题应该怎么处理呢？

时间主要耗费在一开始k个元素的初始建堆O(logk)上，还有删除堆顶元素和插入新元素时的堆化O(logk)上；所以，总的时间复杂度应该为O(nlogk)，比使用排序来获取Top-k的O(nlogn)还是要高效的。

对于一个无序的数列，怎么求出它的中位数呢？这要看数列是静态的还是动态的。

如果是静态的数列，那么我们先进行排序，比如快速排序O(nlogn)，然后如果总数是奇数，那么中位数就在n/2+1的位置上；如果总数是偶数，那么中位数有两个，在n/2和n/2+1的位置上，随便取一个即可。总的时间复杂度就是排序算法的时间复杂度O(nlogn)。

那如果是动态数列呢，我们需要维护数列的有序性，那么势必要对新插入或者需要删除的数据进行查找，时间复杂度为O(n)，还有数据搬移的O(n)，所以就会变得很低效，我们需要使用堆来解决这个问题。

我们先将已有数据排序，然后维护一个大顶堆和一个小顶堆，其中小顶堆存放最大的n/2个数据，堆顶元素是这n/2中最小的，大顶堆存放剩下的元素，堆顶元素是最大的。此时，中位数就是大顶堆的堆顶元素。

当动态数据添加进来时，我们将待添加元素和大顶堆的堆顶元素进行比较，如果小于等于，那么就插入大顶堆中；否则就和小顶堆的堆顶元素比较，如果大于等于，就插入小顶堆中。此时，如果小顶堆中的个数超过了n/2，就需要不断地取出堆顶元素插入到大顶堆中，直至个数为n/2；如果小顶堆中的个数小于n/2，就需要不断地取出大顶堆的堆顶元素插入到小顶堆中，直至小顶堆个数为n/2；

通过如上的过程，我们每次从大顶堆堆顶取出来的元素就是整个数列的中位数。整个过程的时间复杂度是多少呢？一开始初始化时的排序和建堆，由于数据比较少，可以算作常量；后续动态数据的插入或者删除，就是一个堆化的过程，时间复杂度为O(logn)；大顶堆和小顶堆之间元素个数的调整不会有很多元素，所以也算作常数；因此，总的时间复杂度就是O(logn)。

既然动态数列求解中位数使用堆比较好，为什么静态数列求解中位数不使用堆，而是排序呢？静态数列也可以使用如上堆的方案进行求解中位数，但是时间复杂度也是O(nlogn)，和排序是一样的，但是排序明显更加地简单，因此推荐使用排序的方案。

求解中位数的问题其实就是求解百分位数问题的一种特殊情况， 中位数可以理解为百分位为50%，所以把中位数问题一般化的话，那么问题就是求解任意百分位数的问题。

思路和上述求解百分位是一样的，比如我们要求解90%百分位的数，那么大顶堆中需要存放90%的数据，小顶堆中存放10%的数据，当动态地增加时需要依次和大顶堆、小顶堆的堆顶元素进行比较以决定插入到哪个堆中；如果插入或者删除后，小顶堆中的数据占比不是10%了，就需要和大顶堆进行数据的交互以保证小顶堆数据的占比，如此才能保证大顶堆的堆顶元素就是我们需要的百分位数据。

堆排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法。

堆是一种特殊的树。

只要满足这两点，它就是一个堆：

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做 “大顶堆” 。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做 “小顶堆” 。

完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。下标可以直接计算出左右字数的下标。（数组中下标为 i 的节点，左子节点下标为 i∗2 ，右子节点下标为 i∗2+1，父节点的下标为 i/2​ 。）

如果我们把新插入的元素放到堆的最后，你可以看我画的这个图，是不是不符合堆的特性了？于是，我们就需要进行调整，让其重新满足堆的特性，这个过程我们起了一个名字，就叫做 堆化（heapify） 。

堆化实际上有两种，从下往上和从上往下。这里我先讲从下往上的堆化方法。

堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。

我们把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是 从上往下的堆化方法 。

一个包含 n 个节点的完全二叉树，树的高度不会超过 log2​n。堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，也就是 O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化，所以，往堆中插入一个元素和删除堆顶元素的时间复杂度都是 O(logn)。

这里我们借助于堆这种数据结构实现的排序算法，就叫做堆排序。这种排序方法的时间复杂度非常稳定，是 O(nlogn)，并且它还是原地排序算法。

从后往前处理数组，并且每个数据都是从上往下堆化。

因为叶子节点往下堆化只能自己跟自己比较，所以我们直接从最后一个非叶子节点开始，依次堆化就行了。

建堆的时间复杂度就是 O(n)。 推导过程见 极客时间--数据结构与算法之美

建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。

这个过程有点类似上面讲的“删除堆顶元素”的 *** 作，当堆顶元素移除之后，我们把下标为 n 的元素放到堆顶，然后再通过堆化的方法，将剩下的 n−1 个元素重新构建成堆。堆化完成之后，我们再取堆顶的元素，放到下标是 n−1 的位置，一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，排序工作就完成了。

整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。堆排序包括建堆和排序两个 *** 作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。

堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的 *** 作，所以就有可能改变值相同数据的原始相对顺序。

堆这种数据结构几个非常重要的应用：优先级队列、求 Top K 和求中位数。

假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。这里就会用到优先级队列。

这里就可以用到优先级队列，也可以说是堆。我们将从小文件中取出来的字符串放入到小顶堆中，那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。我们将这个字符串放入到大文件中，并将其从堆中删除。然后再从小文件中取出下一个字符串，放入到堆中。循环这个过程，就可以将 100 个小文件中的数据依次放入到大文件中。

我们可以用优先级队列来解决。我们按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先执行的任务。

如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。

中位数，顾名思义，就是处在中间位置的那个数。

使用两个堆：一个大顶堆， 一个小顶堆。 小顶堆中的数据都大于大顶堆中的数据。

如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；否则，我们就将这个新数据插入到小顶堆。

也就是说，如果有 n 个数据，n 是偶数，我们从小到大排序，那前 2n​ 个数据存储在大顶堆中，后 2n​ 个数据存储在小顶堆中。这样，大顶堆中的堆顶元素就是我们要找的中位数。如果 n 是奇数，情况是类似的，大顶堆就存储 2n​+1 个数据，小顶堆中就存储 2n​ 个数据。

极客时间--数据结构与算法之美--28 | 堆和堆排序：为什么说堆排序没有快速排序快？

---