Java篇—“topK”問題詳解（最小堆實作）

topK問題：

從海量資料中擷取最大（或最小）的K個資料。

堆的知識點：

https://blog.csdn.net/weixin_43761659/article/details/97118158

最小堆（小根堆）圖解：

最小堆（小根堆）是一種資料結構，它首先是一顆完全二叉樹，并且，它所有父節點的值都小于或等于兩個子節點的值。如上圖所示：a[0] <= a[1] && a[0] <= a[2] ,a[1] <= a[3] && a[1] <= a[4]...

topK問題分析：

利用堆的特性，小根堆（最小堆）的堆頂元素是最小值，尋找數組中最大的k個元素，要先将數組轉化為小根堆，周遊數組，從第k個下标開始周遊，比堆頂元素大的放入堆中，替換堆頂元素并重新建構小根堆，比堆頂元素小的則跳過即可。

相反，大根堆（最大堆）的堆頂元素是最大值，尋找數組中最小的k個元素，要将數組轉化為大根堆，從第k個下标周遊數組，比堆頂元素小的放入堆中，替換堆頂元素并重新建構大根堆，比堆頂元素大的跳過。

topK問題—最小堆解題思路：

step 1：将普通數組轉化為最小堆，此時數組就符合最小堆的特性：所有父節點的值小于或者等于兩個子節點的值；

step 2：取出數組中的前k個元素，放入自己建立的topK數組當中，并将其建構為小根堆；

step 3：從第k個下标開始周遊數組，擷取堆頂元素root，與data[i] (i=k,k+1,k+2...)進行比較，當data[i] > root時，替換堆頂元素并重新建構小根堆，否則跳過；

step 4：上述步驟進行完畢後，topK數組中的元素就是想要的元素（最大的k個元素），輸出即可。

詳細代碼及注釋：

/**
 * @author:QJJia
 * @description:topK問題
 */
public class MinHeap {
    // 堆的存儲結構 - 一維數組
    private int[] data;
    //構造函數：堆的初始化及小根堆的建立
    public MinHeap(int[] data){
        this.data = data;
        buildHeap();
    }
    //建立最小堆
    private void buildHeap() {
        //從最後一個父節點的下标開始周遊   子推父：(data.length - 1 - 1)/2
        for (int i = (data.length - 1 - 1)/2; i >= 0; i--) {
            heapify(i);
        }
    }
    //最小堆的堆化
    private void heapify(int len) {
        //parent為父節點的下标
        int parent = len;
        //child為左孩子
        int child = 2*parent + 1;
        while(child < data.length){
            //判斷有無右孩子，child+1 < data.length,說明有右孩子,data[child] > data[child+1],說明右孩子為最小值
            if(child + 1 < data.length && data[child] > data[child+1]){
                child++;
            }
            //此時的child為最小值的下标
            //如果父節點大于孩子節點，交換即可
            if(data[parent] > data[child]){
                swap(data,parent,child);
                //孩子節點也可能有孩子節點
                parent = child;
                child = 2*parent + 1;
            }else{
                break;
            }
        }
    }
    //數值交換函數
    private void swap(int[] data, int a, int b) {
        int temp = data[a];
        data[a] = data[b];
        data[b] = temp;
    }
    //擷取堆頂元素
    private int getHeapTop(){
        //如果數組的長度為0，抛出一個異常，否則傳回this.data[0]
        if(this.data.length == 0){
            throw new UnsupportedOperationException("堆為空，無法擷取堆頂元素！");
        }
        return this.data[0];
    }
    //将堆頂元素替換為datum，并重新建構小根堆
    private void addHeap(int datum) {
        this.data[0] = datum;
        //重新建構小根堆
        heapify(0);
    }
    //當資料大于最小堆的堆頂元素時，替換，并重新建構最小堆
    private static int[] topK(int[] data, int k) {
        //建立topK數組
        int[] topK = new int[k];
        //将前k個元素放入topK中
        System.arraycopy(data,0,topK,0,k);
        //将topK建構為小根堆
        MinHeap minHeap = new MinHeap(topK);
        for (int i = k; i < data.length; i++) {
            //用root儲存堆頂元素的值
            int root = minHeap.getHeapTop();
            //比較data元素和堆頂元素
            if(data[i] > root){
                //如果data元素大于堆頂元素，放入堆中，替換堆頂元素，并重新建構小根堆
                minHeap.addHeap(data[i]);
            }
        }
        return topK;
    }
    //測試
    public static void main(String[] args) {
        int[] data = {12,10,4,7,30,9,6,20};
        //提取data中的三個最大元素
        int[] topK = topK(data,3); //12 30 20
        //輸出topK數組中的元素
        for (int i = 0; i < topK.length; i++) {
            System.out.print(topK[i] + " ");
        }
        System.out.println();
    }
}
           

topK問題總結：

什麼時候要建立最小堆：（1）取出前k個元素放入自定義數組中（2）替換堆頂元素，重新建構最小堆時。

心靈雞湯：選好一條路，不輕言放棄，隻為自己買東西的時候，看到名牌标簽，不再糾結猶豫！