数据结构与算法——堆的应用

摘要：我们可以维护一个大小为的小顶堆，然后依次遍历数组，如果数组数据比堆顶元素大，则插入到堆中，如果小，则不做处理。我们可以维护一个大顶堆，一个小顶堆，小顶堆中存储后个数据，大顶堆中存储前面剩余的数据。

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 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 data = new ArrayList<>(Arrays.asList(num));
            //大顶堆
            Queue bigQueue = new PriorityQueue<>((o1, o2) -> {
                if (o1 <= o2) return 1;
                else return -1;
            });
            //小顶堆
            Queue 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 list, int value, Queue bigQueue, Queue 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());
        }
    }