本文共 3416 字，大约阅读时间需要 11 分钟。

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()); }}
        
       
      
     
    
   

转载地址：https://blog.csdn.net/Rose_DuanM/article/details/88616270 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！