要解決 top-k 問題，我們應(yīng)該先熟悉一種數(shù)據(jù)結(jié)構(gòu) - 堆（優(yōu)先級隊(duì)列），已經(jīng)了解的朋友可以跳過哦。

1、什么是堆？

堆結(jié)構(gòu)

堆其實(shí)就是一種二叉樹，但是普通的二叉樹是以鏈?zhǔn)浇Y(jié)構(gòu)進(jìn)行儲存數(shù)據(jù)的，而堆是以數(shù)組進(jìn)行順序存儲數(shù)據(jù)的。那么什么樣的二叉樹才適合用順序存儲的方式呢？

我們假設(shè)一顆普通的二叉樹可以用數(shù)組存儲，那么就可以得到如下結(jié)構(gòu)：

我們可以看到，當(dāng)二叉樹中間有空值時(shí)，數(shù)組的存儲空間會(huì)被浪費(fèi)，那么什么情況下空間才不會(huì)被浪費(fèi)呢？ 那就是完全二叉樹。

從以上結(jié)構(gòu)中，我們不能用鏈?zhǔn)浇Y(jié)構(gòu)的指針來訪問孩子節(jié)點(diǎn)或者父親節(jié)點(diǎn)，只能通過對應(yīng)下標(biāo)來訪問，其實(shí)也比較簡單。

例如下圖：

已知 2 節(jié)點(diǎn)的下標(biāo)是1，那么

他的左孩子下標(biāo)是：2 * 2 + 1 = 3

他的右孩子下標(biāo)是：2 * 2 + 2 = 4

相反，已知 1 節(jié)點(diǎn)的下標(biāo)是3，3 節(jié)點(diǎn)的下標(biāo)是4，那么

1 節(jié)點(diǎn)的父親節(jié)點(diǎn)下標(biāo)是：(3 - 1) / 2 = 1

3 節(jié)點(diǎn)的父親節(jié)點(diǎn)下標(biāo)是：(4 - 1) / 2 = 1

大根堆 VS 小根堆

大根堆（最大堆）

大根堆保證，每顆二叉樹的根節(jié)點(diǎn)都 大于 左右孩子節(jié)點(diǎn)

從最后一棵子樹的根節(jié)點(diǎn)開始調(diào)整，來到每顆子樹的根節(jié)點(diǎn)，使得每棵子樹都向下調(diào)整為大根堆，最后再向下做最后調(diào)整，保證二叉樹整體是大根堆（這個(gè)調(diào)整主要是為了后面的堆排序）。

具體調(diào)整過程如下：

怎么用代碼實(shí)現(xiàn)呢？

我們首先從最后一棵子樹調(diào)整，那么就要拿到最后一顆子樹的根節(jié)點(diǎn) parent ，我們知道數(shù)組最后一個(gè)節(jié)點(diǎn)下標(biāo)是 len - 1，而這個(gè)節(jié)點(diǎn)是最后一棵子樹的左孩子或者右孩子，根據(jù)孩子下標(biāo)就可以拿到根節(jié)點(diǎn)下標(biāo)( parent ) ，parent-- 就可以讓每顆子樹都進(jìn)行調(diào)整，直到來到根節(jié)點(diǎn)，再向下調(diào)整最后一次，便可以得到大根堆。

// 將數(shù)組變成大根堆結(jié)構(gòu)
public void createHeap(int[] arr){
    for (int i = 0; i < arr.length; i++) {
        elem[i] = arr[i];// 放入elem[],假設(shè)不需要擴(kuò)容
        usedSize++;
    }
    // 得到根節(jié)點(diǎn)parent, parent--依次來到每顆子樹的根節(jié)點(diǎn)，
    for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
        // 依次向下搜索，使得每顆子樹都變成大根堆
        shiftDown(parent,usedSize);
    }
}
// 向下搜索變成大根堆
public void shiftDown(int parent,int len){
    int child = parent*2+1;// 拿到左孩子
    while (child < len){
        // 如果有右孩子,比較左右孩子大小,得到較大的值和父節(jié)點(diǎn)比較 
        if (child+1 < len && (elem[child] < elem[child+1])){
            child++;
        }
        // 比較較大的孩子和父節(jié)點(diǎn),看是否要交換
        int max = elem[parent] >= elem[child] ? parent : child;
        if (max == parent) break;// 如果不需要調(diào)整了，說明當(dāng)前子樹已經(jīng)是大根堆了，直接 break
        swap(elem,parent,child);
        parent = child;// 繼續(xù)向下檢測，看是否要調(diào)整
        child = parent*2+1;
    }
}
public void swap(int[] arr,int i,int j){
  	int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

小根堆（最小堆）

小根堆保證，每顆二叉樹的根節(jié)點(diǎn)都 小于 左右孩子節(jié)點(diǎn)

調(diào)整過程同上。

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

在java中，提供了堆這種數(shù)據(jù)結(jié)構(gòu)（PriorityQueue），也叫優(yōu)先級隊(duì)列，當(dāng)我們創(chuàng)建一個(gè)這樣的對象時(shí)，就得到了一個(gè)沒有添加數(shù)據(jù)的 小根堆 ，我們可以向里面添加或者刪除元素，每向里面刪除或者添加一個(gè)元素，系統(tǒng)會(huì)整體進(jìn)行一次調(diào)整，重新又調(diào)整為小根堆。

// 默認(rèn)得到一個(gè)小根堆
PriorityQueue<Integer> smallHeap = new PriorityQueue<>();
smallHeap.offer(23);
smallHeap.offer(2);
smallHeap.offer(11);
System.out.println(smallHeap.poll());// 彈出2，剩余最小的元素就是11，會(huì)被調(diào)整到堆頂，下一次彈出
System.out.println(smallHeap.poll());// 彈出11

 // 如果需要得到大根堆，在里面?zhèn)饕粋€(gè)比較器
 PriorityQueue<Integer> BigHeap = new PriorityQueue<>(new Comparator<Integer>() {
     @Override
     public int compare(Integer o1, Integer o2) {
         return o2 - o1;
     }
 });

2、top-k問題解決思路

例：有一堆元素，讓你找出前三個(gè)最小的元素。

思路一： 將數(shù)組從小到大排序，拿到數(shù)組前3個(gè)元素。但是可以發(fā)現(xiàn)這樣時(shí)間復(fù)雜度太高，不可取。

思路二： 將元素全部放入一個(gè)堆結(jié)構(gòu)中，然后彈出三個(gè)元素，每次彈出的元素都是當(dāng)前堆最小的，那么彈出的三個(gè)元素就是前最小的三個(gè)元素。

這種思路可以做，但是假設(shè)我有1000000個(gè)元素，只彈出前三個(gè)最小的元素，那么就要用到大小為1000000的堆。這么做空間復(fù)雜度太高，不建議用這種方法。

思路三：

我們需要得到三個(gè)最小的元素，那么就建一個(gè)大小為3的堆，假設(shè)目前的堆結(jié)構(gòu)中剛好放滿了3個(gè)元素，那么這三個(gè)元素就是當(dāng)前最小的三個(gè)元素。假設(shè)第四個(gè)元素是我們想要的元素之一，那么前三個(gè)至少有一個(gè)元素不是我們想要的，就需要彈出，那么彈出誰呢？

我們要得到的是前三個(gè)最小的元素，所以當(dāng)前堆結(jié)構(gòu)中最大的元素一定不是我們想要的，所以這里我們建一個(gè)大根堆。彈出該元素，然后放入第四個(gè)元素，直到遍歷完整個(gè)數(shù)組。

這樣我們就得到了只含有前三個(gè)最小元素的堆，并且可以看到堆的大小一直都是3，而不是有多少數(shù)據(jù)就建多大的堆，然后再依次彈出元素就行了。

// 找前 k個(gè)最小的元素
public static int[] topK(int[] arr,int k){
     // 創(chuàng)建一個(gè)大小為 k的大根堆
     PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,new Comparator<Integer>() {
         @Override
         public int compare(Integer o1, Integer o2) {
             return o2 - o1;
         }
     });
     for (int i = 0; i < arr.length; i++) {
         if (i < k){
             // 放入前 k 個(gè)元素
             maxHeap.offer(arr[i]);
         }else{
             // 從第 k+1個(gè)元素開始進(jìn)行判斷是否要入堆
             if (maxHeap.peek() > arr[i]){
                 maxHeap.poll();
                 maxHeap.offer(arr[i]);
             }
         }
     }
     int[] ret = new int[k];
     for (int i = 0; i < k; i++) {
         ret[i] = maxHeap.poll();
     }
     return ret;
 }

以上就是top-k問題的基本思路，其他的類似問題也是這樣解。

總結(jié)：

1、如果求前K個(gè)最大的元素，要建一個(gè)小根堆。

2、如果求前K個(gè)最小的元素，要建一個(gè)大根堆。

3、如果求第K大的元素，要建一個(gè)小根堆 ( 堆頂元素就是 )。

4、如果求第K小的元素，要建一個(gè)大根堆 ( 堆頂元素就是 )。

到此這篇關(guān)于Java 詳細(xì)講解用堆解決Top-k問題的文章就介紹到這了,更多相關(guān)Java Top-k問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論