---

前言

本篇文章進行如何用堆結構解決TOP-K問題的講解

---

一、TOP-K問題是什么？

TOP-k問題：即求一些數據中的前k個最大的數字或最小的數字，并且一般這些數據規模都很大

生活中也有許多常見的topks問題，比如在打游戲時的全服前幾名玩家，世界五百強，專業前十名等等，這些都屬于TOP-K問題

而當數據規模很大的時候，想要找出前k個最大值或最小值，普通排序是難以滿足要求的，因為時間復雜度太高，比如冒泡排序，這就讓我們聯想到了一種排序方式——堆排序

因為我們想要找到前k個最大值或最小值，必然離不開排序，并且當數據規模極大的時候，我們不可能全部等待它加載出來，這時候我們常常借助堆這個結構來解決

舉個例子，當我們需要找出100億個整數的前k個最大值的時候，這100億個整數我們不可能全部申請到內存中，我們計算一下，100億個整數，相當于400億個字節

而1G = 1024MB = 1024 * 1024KB = 1024 * 1024 * 1024Byte，1個G，大約是10億個字節，那么400億個字節，就相當于40G的內存，注意，這是臨時申請的內存，是運行內存，我們想想，一個普通的筆記本電腦運行內存才有多少，這一下子就占據了40G，除去電腦本身的操作系統等也需要使用占據的運行內存，我們的電腦內存能承受得住嗎，而且我們申請完空間之后，還要借助cpu進行排序等操作，換句話說，cpu內心可能在哀嚎：皇上，臣妾做不到啊！

而這時候，就輪到了我們的堆同學出場了

二、如何用堆解決TOP-K問題

1.怎么建堆，建大堆還是小堆？

當我們想要取N個數據的前k個最大元素時，我們要建小堆

當取前k個最小元素時，我們要建大堆

可能有些同學會想到上一篇剛剛講到的堆排序問題，堆排序，升序建大堆，降序建小堆，為什么到TOP-K問題就變了呢？

因為我們要解決的TOP-K問題，通常數據規模較大，并且它只要求我們找到前k個最大數據，并不要求對數據整體進行排序，因此我們并不一定要按照堆排序的方式進行，只需要進行類似于“排序”的操作，找出前k個最大值即可，對整體數據進行排序反而會讓問題變得更加復雜，有些冗余

如果我們按照堆排序的想法進行，在N個數據中找到前k個最大元素，那么就要建N個大堆，然后再pop（刪除）K次，最后得到前k個最大元素，在這個過程中，整個數據的順序也排成了升序，這未免有些冗雜，因此我們要采取另一種方式

我們以N個數據中取前K個最大元素為例，此時我們要建小堆，并且只用數據中的前k個元素進行建堆，當我們對數據中前k個元素建小堆之后，堆頂的元素則是前k個元素中最小的那一個元素，剩下的N - K個元素逐個與堆頂元素進行比較，如果剩下的元素比堆頂元素大的話，就將堆頂元素進行替換，替換為更大的那個元素，替換后將前k個數據建成的小堆進行向下調整，調整之后繼續將堆頂元素和后面的元素進行比較，重復進行

這種方式會使得最開始的前k個元素中的最小值“沉底”，而替換上來的是一個大一點的元素，向下調整之后，堆頂的數據又是前k個元素中最小的那一個，再與剩下的元素進行比較，這樣我們就不必擔心大的數據會遺漏，因為我們建的是小堆，小堆的堆頂元素必然是最小的，大一些的元素都是堆頂元素的子結點，不必擔心小的數據會進入導致出錯

有的同學可能會問，既然這樣，建大堆不行嗎？

答案是不行！

如果我們以這種方式進行并且建大堆的話，那么堆頂元素存儲的則是前k中最大的元素，我們無法確定堆頂元素的子結點與剩下的N - K個結點之間的大小，可能會造成大的元素無法進入，比如堆頂是100，子結點中有的數據是5、10、15等等，剩下的N-K個元素中如果有78，那么判定78 < 100，不替換，78就無法進入前k個元素建成的小堆，但是實際上78是大于5、10、15這些數的，這就會導致出錯，甚至可能會導致前k中只有最大的元素和最小的k - 1個元素，因此當我們取前k個最大元素時，建大堆并不可取。

建大堆適合于取前k個最小元素時，這時候小于堆頂元素的就進行替換，替換之后向下調整，再重復，最后前k個元素自然就是最小的前k個元素

并且當我們如此操作時，我們只需要維護建堆的那k個空間即可，因為我們進行的是替換操作，不符合條件的堆頂元素直接就被替換，被丟棄掉，不需要再維護了，而且我們這種方式，不必擔心被丟棄的元素會比后面的元素大，成為前k個最大元素之一，因為它既然是堆頂元素，必然是前k個元素建成的小堆中的最小的一個元素，被替換后，替換上的數據必然會比它要大，而堆中剩下的k -1 個元素也必然大于它，因此替換后的前k個元素都是比被替換的元素要大的，后面如果繼續替換，說明它一定大于之前被替換的元素，就像b>a,a被替換，后面再比較，c > b，那么b被替換，此時c一定是大于a的，之后再進行重復比較、替換、調整，不會出現錯誤

2.代碼實現

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//topk問題，找出最大的k個數，那么就要建小堆
void Swap(int* a, int* b)
{int tmp;tmp = *a;*a = *b;*b = tmp;
}
void AdjustDown(int*a ,int n,int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]){child += 1;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void Topk(int* a,int n,int k)
{assert(k > 0 && k <= n);for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, k, i);}for (int i = k; i < n; i++){if (a[i] > a[0]){Swap(&a[0], &a[i]);AdjustDown(a, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", a[i]);}
}
int main()
{int n;int k;printf("請輸入你要輸入數字的個數:");scanf_s("%d", &n);printf("請輸入你要查找的前k個最大數的個數k");scanf_s("%d", &k);int* a = (int*)malloc(sizeof(int) * n);if (a == NULL){perror("malloc fail");return 0;}printf("請輸入n個數字");for (int i = 0; i < n; i++){scanf_s("%d", &a[i]);}Topk(a, n, k);free(a);a = NULL;return 0;
}

與堆排序類似，我們依舊是先進行向下調整模擬建堆（為什么采用向下調整模擬建堆詳見上篇文章），之后進行比較、交換、調整，重復操作，當然，當數據規模過大的時候，我們一般不采取圖中的主函數中依次輸入后讀取數據的方式，多采用造文件，從文件中讀取數據的方式進行測試或者其他操作，具體詳見文件操作篇

總結

本篇講解了如何使用堆結構去解決TOP-K問題，關于TOP-K還有許多解法，比如隨機選擇等，后續會繼續發布，敬請關注！