Java最小堆解決TopK問題

其實我們與大資料并不遙遠，比如要從海量資料中按大小或頻率挑出top k，假定機器是多核的記憶體有限的，我們采用多線程分塊處理資料，最後合并處理。那麼，處理每一塊資料的top k(i)可以采用哪些算法呢？

topk問題是指從大量資料（源資料）中擷取最大（或最小）的k個資料。

topk問題是個很常見的問題：例如學校要從全校學生中找到成績最高的500名學生，再例如某搜尋引擎要統計每天的100條搜尋次數最多的關鍵詞。

對于這個問題，解決方法有很多：

方法一：對源資料中所有資料進行排序，取出前k個資料，就是topk。

但是當資料量很大時，隻需要k個最大的數，整體排序很耗時，效率不高。

方法二：維護一個k長度的數組a[]，先讀取源資料中的前k個放入數組，對該數組進行升序排序，再依次讀取源資料第k個以後的資料，和數組中最小的元素（a[0]）比較，如果小于a[0]直接pass，大于的話，就丢棄最小的元素a[0]，利用二分法找到其位置，然後該位置前的數組元素整體向前移位，直到源資料讀取結束。

這比方法一效率會有很大的提高，但是當k的值較大的時候，長度為k的資料整體移位，也是非常耗時的。

對于這種問題，效率比較高的解決方法是使用最小堆。

最小堆的存儲結構（實體結構）實際上是一個數組。如下圖：

堆有幾個重要操作：

buildheap：将普通數組轉換成堆，轉換完成後，數組就符合堆的特性：所有父節點的值小于或等于兩個子節點的值。

heapify(int i)：當元素i的左右子樹都是小根堆時，通過heapify讓i元素下降到适當的位置，以符合堆的性質。

回到上面的取topk問題上，用最小堆的解決方法就是：先取源資料中的k個元素放到一個長度為k的數組中去，再把數組轉換成最小堆。再依次取源資料中的k個之後的資料和堆的根節點（數組的第一個元素）比較，根據最小堆的性質，根節點一定是堆中最小的元素，如果小于它，則直接pass，大于的話，就替換掉跟元素，并對根元素進行heapify，直到源資料周遊結束。

最小堆的實作：

public class minheap  

{  

    // 堆的存儲結構 - 數組  

    private int[] data;  

    // 将一個數組傳入構造方法，并轉換成一個小根堆  

    public minheap(int[] data)  

    {  

        this.data = data;  

        buildheap();  

    }  

    // 将數組轉換成最小堆  

    private void buildheap()  

        // 完全二叉樹隻有數組下标小于或等于 (data.length) / 2 - 1 的元素有孩子結點，周遊這些結點。  

        // *比如上面的圖中，數組有10個元素， (data.length) / 2 - 1的值為4，a[4]有孩子結點，但a[5]沒有*  

        for (int i = (data.length) / 2 - 1; i >= 0; i--)   

        {  

            // 對有孩子結點的元素heapify  

            heapify(i);  

        }  

    private void heapify(int i)  

        // 擷取左右結點的數組下标  

        int l = left(i);    

        int r = right(i);  

        // 這是一個臨時變量，表示 跟結點、左結點、右結點中最小的值的結點的下标  

        int smallest = i;  

        // 存在左結點，且左結點的值小于根結點的值  

        if (l < data.length && data[l] < data[i])    

            smallest = l;    

        // 存在右結點，且右結點的值小于以上比較的較小值  

        if (r < data.length && data[r] < data[smallest])    

            smallest = r;    

        // 左右結點的值都大于根節點，直接return，不做任何操作  

        if (i == smallest)    

            return;    

        // 交換根節點和左右結點中最小的那個值，把根節點的值替換下去  

        swap(i, smallest);  

        // 由于替換後左右子樹會被影響，是以要對受影響的子樹再進行heapify  

        heapify(smallest);  

    // 擷取右結點的數組下标  

    private int right(int i)  

    {    

        return (i + 1) << 1;    

    }     

    // 擷取左結點的數組下标  

    private int left(int i)   

        return ((i + 1) << 1) - 1;    

    // 交換元素位置  

    private void swap(int i, int j)   

        int tmp = data[i];    

        data[i] = data[j];    

        data[j] = tmp;    

    // 擷取對中的最小的元素，根元素  

    public int getroot()  

            return data[0];  

    // 替換根元素，并重新heapify  

    public void setroot(int root)  

        data[0] = root;  

        heapify(0);  

}  

利用最小堆擷取topk：

public class topk  

    public static void main(string[] args)  

        // 源資料  

        int[] data = {56,275,12,6,45,478,41,1236,456,12,546,45};  

// 擷取top5  

        int[] top5 = topk(data, 5);  

        for(int i=0;i<5;i++)  

            system.out.println(top5[i]);  

    // 從data數組中擷取最大的k個數  

    private static int[] topk(int[] data,int k)  

        // 先取k個元素放入一個數組topk中  

        int[] topk = new int[k];   

        for(int i = 0;i< k;i++)  

            topk[i] = data[i];  

        // 轉換成最小堆  

        minheap heap = new minheap(topk);  

        // 從k開始，周遊data  

        for(int i= k;i<data.length;i++)  

            int root = heap.getroot();  

            // 當資料大于堆中最小的數（根節點）時，替換堆中的根節點，再轉換成堆  

            if(data[i] > root)  

            {  

                heap.setroot(data[i]);  

            }  

        return topk;  

介紹完了最小堆，顧名思義，相應的還有最大堆。

www.toutiao.im

系統可用記憶體10m，從一個2g的文本檔案裡統計出現次數排名前10的單詞，用mapreduce再合适不過，分而治之。

原文連結:[http://wely.iteye.com/blog/2353982]