轉(zhuǎn)載自??Java最小堆解決TopK問(wèn)題

TopK問(wèn)題是指從大量數(shù)據(jù)（源數(shù)據(jù)）中獲取最大（或最小）的K個(gè)數(shù)據(jù)。

TopK問(wèn)題是個(gè)很常見(jiàn)的問(wèn)題：例如學(xué)校要從全校學(xué)生中找到成績(jī)最高的500名學(xué)生，再例如某搜索引擎要統(tǒng)計(jì)每天的100條搜索次數(shù)最多的關(guān)鍵詞。

對(duì)于這個(gè)問(wèn)題，解決方法有很多：

方法一：對(duì)源數(shù)據(jù)中所有數(shù)據(jù)進(jìn)行排序，取出前K個(gè)數(shù)據(jù)，就是TopK。

但是當(dāng)數(shù)據(jù)量很大時(shí)，只需要k個(gè)最大的數(shù)，整體排序很耗時(shí)，效率不高。
?

方法二：維護(hù)一個(gè)K長(zhǎng)度的數(shù)組a[]，先讀取源數(shù)據(jù)中的前K個(gè)放入數(shù)組，對(duì)該數(shù)組進(jìn)行升序排序，再依次讀取源數(shù)據(jù)第K個(gè)以后的數(shù)據(jù)，和數(shù)組中最小的元素（a[0]）比較，如果小于a[0]直接pass，大于的話，就丟棄最小的元素a[0]，利用二分法找到其位置，然后該位置前的數(shù)組元素整體向前移位，直到源數(shù)據(jù)讀取結(jié)束。

這比方法一效率會(huì)有很大的提高，但是當(dāng)K的值較大的時(shí)候，長(zhǎng)度為K的數(shù)據(jù)整體移位，也是非常耗時(shí)的。

對(duì)于這種問(wèn)題，效率比較高的解決方法是使用最小堆。

最小堆（小根堆）是一種數(shù)據(jù)結(jié)構(gòu)，它首先是一顆完全二叉樹(shù)，并且，它所有父節(jié)點(diǎn)的值小于或等于兩個(gè)子節(jié)點(diǎn)的值。

最小堆的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）實(shí)際上是一個(gè)數(shù)組。如下圖：

堆有幾個(gè)重要操作：

BuildHeap：將普通數(shù)組轉(zhuǎn)換成堆，轉(zhuǎn)換完成后，數(shù)組就符合堆的特性：所有父節(jié)點(diǎn)的值小于或等于兩個(gè)子節(jié)點(diǎn)的值。

Heapify(int i)：當(dāng)元素i的左右子樹(shù)都是小根堆時(shí)，通過(guò)Heapify讓i元素下降到適當(dāng)?shù)奈恢?#xff0c;以符合堆的性質(zhì)。

回到上面的取TopK問(wèn)題上，用最小堆的解決方法就是：先去源數(shù)據(jù)中的K個(gè)元素放到一個(gè)長(zhǎng)度為K的數(shù)組中去，再把數(shù)組轉(zhuǎn)換成最小堆。再依次取源數(shù)據(jù)中的K個(gè)之后的數(shù)據(jù)和堆的根節(jié)點(diǎn)（數(shù)組的第一個(gè)元素）比較，根據(jù)最小堆的性質(zhì)，根節(jié)點(diǎn)一定是堆中最小的元素，如果小于它，則直接pass，大于的話，就替換掉跟元素，并對(duì)根元素進(jìn)行Heapify，直到源數(shù)據(jù)遍歷結(jié)束。

最小堆的實(shí)現(xiàn)：

public class MinHeap { // 堆的存儲(chǔ)結(jié)構(gòu) - 數(shù)組 private int[] data; // 將一個(gè)數(shù)組傳入構(gòu)造方法，并轉(zhuǎn)換成一個(gè)小根堆 public MinHeap(int[] data) { this.data = data; buildHeap(); } // 將數(shù)組轉(zhuǎn)換成最小堆 private void buildHeap() { // 完全二叉樹(shù)只有數(shù)組下標(biāo)小于或等于 (data.length) / 2 - 1 的元素有孩子結(jié)點(diǎn)，遍歷這些結(jié)點(diǎn)。 // *比如上面的圖中，數(shù)組有10個(gè)元素， (data.length) / 2 - 1的值為4，a[4]有孩子結(jié)點(diǎn)，但a[5]沒(méi)有* for (int i = (data.length) / 2 - 1; i >= 0; i--) { // 對(duì)有孩子結(jié)點(diǎn)的元素heapify heapify(i); } } private void heapify(int i) { // 獲取左右結(jié)點(diǎn)的數(shù)組下標(biāo) int l = left(i); int r = right(i); // 這是一個(gè)臨時(shí)變量，表示 跟結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)中最小的值的結(jié)點(diǎn)的下標(biāo) int smallest = i; // 存在左結(jié)點(diǎn)，且左結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值 if (l < data.length && data[l] < data[i]) smallest = l; // 存在右結(jié)點(diǎn)，且右結(jié)點(diǎn)的值小于以上比較的較小值 if (r < data.length && data[r] < data[smallest]) smallest = r; // 左右結(jié)點(diǎn)的值都大于根節(jié)點(diǎn)，直接return，不做任何操作 if (i == smallest) return; // 交換根節(jié)點(diǎn)和左右結(jié)點(diǎn)中最小的那個(gè)值，把根節(jié)點(diǎn)的值替換下去 swap(i, smallest); // 由于替換后左右子樹(shù)會(huì)被影響，所以要對(duì)受影響的子樹(shù)再進(jìn)行heapify heapify(smallest); } // 獲取右結(jié)點(diǎn)的數(shù)組下標(biāo) private int right(int i) { return (i + 1) << 1; } // 獲取左結(jié)點(diǎn)的數(shù)組下標(biāo) 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; } // 獲取對(duì)中的最小的元素，根元素 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) { // 源數(shù)據(jù) 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數(shù)組中獲取最大的k個(gè)數(shù) private static int[] topK(int[] data,int k) { // 先取K個(gè)元素放入一個(gè)數(shù)組topk中 int[] topk = new int[k]; for(int i = 0;i< k;i++) { topk[i] = data[i]; } // 轉(zhuǎn)換成最小堆 MinHeap heap = new MinHeap(topk); // 從k開(kāi)始，遍歷data for(int i= k;i<data.length;i++) { int root = heap.getRoot(); // 當(dāng)數(shù)據(jù)大于堆中最小的數(shù)（根節(jié)點(diǎn)）時(shí)，替換堆中的根節(jié)點(diǎn)，再轉(zhuǎn)換成堆 if(data[i] > root) { heap.setRoot(data[i]); } } return topk; } }

?

?

?

總結(jié)

以上是生活随笔為你收集整理的Java最小堆解决TopK问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。