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

1.  概述

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

優(yōu)先級隊(duì)列

求 Top K 問題

求中位數(shù)

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

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

而堆其實(shí)就可以看作是一個(gè)優(yōu)先級隊(duì)列，因?yàn)槎秧斣乜偸菙?shù)據(jù)中最大或最小的元素，每次出隊(duì)列都可以看作取出堆頂元素。

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

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

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

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

3.  Top K 問題

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

這分為了兩種情況，一是針對 靜態(tài)數(shù)據(jù) ，即數(shù)據(jù)不會(huì)發(fā)生變化。我們可以維護(hù)一個(gè)大小為 K 的小頂堆，然后依次遍歷數(shù)組，如果數(shù)組數(shù)據(jù)比堆頂元素大，則插入到堆中，如果小，則不做處理。遍歷完之后，則堆中存在的數(shù)據(jù)就是 Top K 了。我用代碼模擬了這個(gè)過程：

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

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

4.  求中位數(shù)

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

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

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

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

我用代碼簡單模擬了整個(gè)實(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());
        }
    }