摘要：我們可以維護一個大小為的小頂堆，然后依次遍歷數(shù)組，如果數(shù)組數(shù)據(jù)比堆頂元素大，則插入到堆中，如果小，則不做處理。我們可以維護一個大頂堆，一個小頂堆，小頂堆中存儲后個數(shù)據(jù)，大頂堆中存儲前面剩余的數(shù)據(jù)。

1.  概述

前面說完了堆這種數(shù)據(jù)結(jié)構(gòu)，并且講到了它很經(jīng)典的一個應(yīng)用：堆排序，其實堆這種數(shù)據(jù)結(jié)構(gòu)還有其他很多的應(yīng)用，今天就一起來看看，主要有下列內(nèi)容：

優(yōu)先級隊列

求 Top K 問題

求中位數(shù)

2.  優(yōu)先級隊列

優(yōu)先級隊列是一種特殊的隊列，前面學(xué)習(xí)隊列的時候，說到隊列滿足 先進先出，后進后出 的特點，優(yōu)先級隊列則不是這樣。優(yōu)先級隊列中的數(shù)據(jù)，出隊的順序是有優(yōu)先級的，優(yōu)先級高的，先出隊列。

而堆其實就可以看作是一個優(yōu)先級隊列，因為堆頂元素總是數(shù)據(jù)中最大或最小的元素，每次出隊列都可以看作取出堆頂元素。

如果你熟悉 Java 語言，則或多或少聽說或是使用過 PriorityQueue 這個容器，在《Java 核心技術(shù)·卷 I》中，說到 PriorityQueue 就是優(yōu)先級隊列，并且它基于一種很優(yōu)雅的數(shù)據(jù)結(jié)構(gòu)——堆。

接下來就小試牛刀，舉一個具體的例子來看看優(yōu)先級隊列的應(yīng)用。例如我們需要合并 10 個有序的小文件，小文件中存儲的是有序的字符串?dāng)?shù)據(jù)。借助優(yōu)先級隊列，我們可以很高效的解決這個問題。

我們從每個文件中讀取第一個字符串存入優(yōu)先級隊列中，那么每次出隊列，都是最小的那個元素。將出隊列的數(shù)據(jù)存儲到一個大文件中，然后繼續(xù)從文件中讀取一個字符串存入隊列，然后繼續(xù)出隊列，一直循環(huán)這個操作。

當(dāng)然，這主要是針對數(shù)據(jù)文件較大的情況，如果數(shù)據(jù)不多，那么直接將全部的數(shù)據(jù)存入隊列，然后依次出隊列就可以了，具體問題具體分析。

3.  Top K 問題

這樣的問題其實非常的常見了，在一組數(shù)據(jù)當(dāng)中 ，我們需要求得其前 K 大的數(shù)據(jù)。

這分為了兩種情況，一是針對 靜態(tài)數(shù)據(jù) ，即數(shù)據(jù)不會發(fā)生變化。我們可以維護一個大小為 K 的小頂堆，然后依次遍歷數(shù)組，如果數(shù)組數(shù)據(jù)比堆頂元素大，則插入到堆中，如果小，則不做處理。遍歷完之后，則堆中存在的數(shù)據(jù)就是 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());
    }
}

第二種情況，是動態(tài)的數(shù)據(jù)集合，數(shù)據(jù)會有增加、刪除的情況，如果新增一個元素，將其和堆頂元素進行比較，如果數(shù)據(jù)比堆頂元素大，則插入到堆中，如果小，則不做處理。這樣的話，無論數(shù)據(jù)怎樣變化，我們都能夠隨時拿到 Top K，而不用因為數(shù)據(jù)的變化重新組織堆。

4.  求中位數(shù)

顧名思義，中位數(shù)就是一組數(shù)據(jù)中最中間的那個數(shù)據(jù)，只不過注意，數(shù)據(jù)需要有序排列。針對一個大小為 n 的數(shù)據(jù)集，如果 n 為偶數(shù)，那么中位數(shù)有兩個，分別是 n/2 和 n/2 + 1 這兩個數(shù)據(jù)，我們可以隨機取其中一個；如果 n 為奇數(shù)，則 n/2 + 1 這個數(shù)為中位數(shù)。

如果是一個靜態(tài)的數(shù)據(jù)，那么可直接排序然后求中位數(shù)，但是如果數(shù)據(jù)有變化，這樣每次排序的成本太高了。所以，可以借助堆來實現(xiàn)求中位數(shù)的功能。

我們可以維護一個大頂堆，一個小頂堆，小頂堆中存儲后 n/2 個數(shù)據(jù)，大頂堆中存儲前面剩余的數(shù)據(jù)。如果 n 是偶數(shù)，則兩個堆中存儲的都是相同個數(shù)的數(shù)據(jù)，如果 n 為奇數(shù)，則大頂堆中要多一個數(shù)據(jù)。結(jié)合下圖你就很容易明白了：

如果有數(shù)據(jù)插入的情況，如果數(shù)據(jù)小于等于大頂堆頂元素，則插入到大頂堆中，如果數(shù)據(jù)大于等于小頂堆頂元素，則插入到小頂堆中。只不過可能會出現(xiàn)一個問題，就是堆中的數(shù)據(jù)不滿足均分情況，那么我們需要移動兩個堆中的元素，反正需要保證 大頂堆的元素個數(shù)和小頂堆的元素個數(shù)要么相等，或者大頂堆中多一個。

我用代碼簡單模擬了整個實現(xiàn)：

    public class GetMiddleNum {
        public static void main(String[] args) {
            //原始數(shù)據(jù)
            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 的數(shù)據(jù)存入到小頂堆中
            for (int j = i; j < n; j++) {
                smallQueue.add(data.get(j));
            }
            //前面的數(shù)據(jù)存入到大頂堆中
            for (int j = 0; j < i; j++) {
                bigQueue.add(data.get(j));
            }
    
            //插入數(shù)據(jù)，需要做多帶帶的處理
            insert(data, 99, bigQueue, smallQueue);
            insert(data, 3, bigQueue, smallQueue);
            insert(data, 1, bigQueue, smallQueue);
    
            //大頂堆的堆頂元素就是中位數(shù)
            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());
        }
    }