共计 2729 个字符，预计需要花费 7 分钟才能阅读完成。
1. 概述
前面说完了堆这种数据结构，并且讲到了它很经典的一个应用：堆排序，其实堆这种数据结构还有其他很多的应用，今天就一起来看看，主要有下列内容：
优先级队列
求 Top K 问题
求中位数
2. 优先级队列
优先级队列是一种特殊的队列，前面学习队列的时候，说到队列满足 先进先出，后进后出 的特点，优先级队列则不是这样。优先级队列中的数据，出队的顺序是有优先级的，优先级高的，先出队列。
而堆其实就可以看作是一个优先级队列，因为堆顶元素总是数据中最大或最小的元素，每次出队列都可以看作取出堆顶元素。
如果你熟悉 Java 语言，则或多或少听说或是使用过 PriorityQueue 这个容器，在《Java 核心技术·卷 I》中，说到 PriorityQueue 就是优先级队列，并且它基于一种很优雅的数据结构——堆。
接下来就小试牛刀，举一个具体的例子来看看优先级队列的应用。例如我们需要合并 10 个有序的小文件，小文件中存储的是有序的字符串数据。借助优先级队列，我们可以很高效的解决这个问题。
我们从每个文件中读取第一个字符串存入优先级队列中，那么每次出队列，都是最小的那个元素。将出队列的数据存储到一个大文件中，然后继续从文件中读取一个字符串存入队列，然后继续出队列，一直循环这个操作。
当然，这主要是针对数据文件较大的情况，如果数据不多，那么直接将全部的数据存入队列，然后依次出队列就可以了，具体问题具体分析。
3. Top K 问题
这样的问题其实非常的常见了，在一组数据当中，我们需要求得其前 K 大的数据。
这分为了两种情况，一是针对 静态数据，即数据不会发生变化。我们可以维护一个大小为 K 的小顶堆，然后依次遍历数组，如果数组数据比堆顶元素大，则插入到堆中，如果小，则不做处理。遍历完之后，则堆中存在的数据就是 Top K 了。我用代码模拟了这个过程：
public class GetTopK {
public static void main(String[] args) {
int[] num = {2, 34, 45, 56, 76, 65, 678, 33, 888, 678, 98, 0, 7};
// 求 Top 3
Queue<Integer> queue = new PriorityQueue<>(3);
queue.add(num[0]);
queue.add(num[1]);
queue.add(num[2]);
for (int i = 3; i < num.length; i++) {
int small = queue.peek();
if (num[i] > small){
queue.poll();
queue.add(num[i]);
}
}
System.out.println(queue.toString());
}
}
第二种情况，是动态的数据集合，数据会有增加、删除的情况，如果新增一个元素，将其和堆顶元素进行比较，如果数据比堆顶元素大，则插入到堆中，如果小，则不做处理。这样的话，无论数据怎样变化，我们都能够随时拿到 Top K，而不用因为数据的变化重新组织堆。
4. 求中位数
顾名思义，中位数就是一组数据中最中间的那个数据，只不过注意，数据需要有序排列。针对一个大小为 n 的数据集，如果 n 为偶数，那么中位数有两个，分别是 n/2 和 n/2 + 1 这两个数据，我们可以随机取其中一个；如果 n 为奇数，则 n/2 + 1 这个数为中位数。
如果是一个静态的数据，那么可直接排序然后求中位数，但是如果数据有变化，这样每次排序的成本太高了。所以，可以借助堆来实现求中位数的功能。
我们可以维护一个大顶堆，一个小顶堆，小顶堆中存储后 n/2 个数据，大顶堆中存储前面剩余的数据。如果 n 是偶数，则两个堆中存储的都是相同个数的数据，如果 n 为奇数，则大顶堆中要多一个数据。结合下图你就很容易明白了：
如果有数据插入的情况，如果数据小于等于大顶堆顶元素，则插入到大顶堆中，如果数据大于等于小顶堆顶元素，则插入到小顶堆中。只不过可能会出现一个问题，就是堆中的数据不满足均分情况，那么我们需要移动两个堆中的元素，反正需要保证 大顶堆的元素个数和小顶堆的元素个数要么相等，或者大顶堆中多一个。
我用代码简单模拟了整个实现：
public class GetMiddleNum {
public static void main(String[] args) {
// 原始数据
Integer[] num = {12, 34, 6, 43, 78, 65, 42, 33, 5, 8};
// 排序后存入 ArrayList 中
Arrays.sort(num);
ArrayList<Integer> data = new ArrayList<>(Arrays.asList(num));
// 大顶堆
Queue<Integer> bigQueue = new PriorityQueue<>((o1, o2) -> {
if (o1 <= o2) return 1;
else return -1;
});
// 小顶堆
Queue<Integer> smallQueue = new PriorityQueue<>();
int n = data.size();
int i;
if (n % 2 == 0) i = n / 2;
else i = n / 2 + 1;
// 后 n/2 的数据存入到小顶堆中
for (int j = i; j < n; j++) {
smallQueue.add(data.get(j));
}
// 前面的数据存入到大顶堆中
for (int j = 0; j < i; j++) {
bigQueue.add(data.get(j));
}
// 插入数据，需要做单独的处理
insert(data, 99, bigQueue, smallQueue);
insert(data, 3, bigQueue, smallQueue);
insert(data, 1, bigQueue, smallQueue);
// 大顶堆的堆顶元素就是中位数
System.out.println(“The middle num = ” + bigQueue.peek());
}
private static void insert(List<Integer> list, int value, Queue<Integer> bigQueue, Queue<Integer> smallQueue){
list.add(value);
if (value <= bigQueue.peek())
bigQueue.add(value);
if (value >= smallQueue.peek())
smallQueue.add(value);
while (smallQueue.size() > bigQueue.size())
bigQueue.add(smallQueue.poll());
while (bigQueue.size() – smallQueue.size() > 1)
smallQueue.add(bigQueue.poll());
}
}
