八十四、堆排序解決TopK問題

「@Author：Runsen」

上次介紹了堆排序，這次介紹堆排序常見的應(yīng)用場景TopK問題。

利用堆求TopK問題

TopK問題是一個堆排序典型的應(yīng)用場景。

題目是這樣的：假設(shè)，我們想在大量的數(shù)據(jù)，如 100 億個整型數(shù)據(jù)中，找到值最大的 K 個元素，K 小于 10000。對此，你會怎么做呢？

對標(biāo)的是Leetcode第215題：「數(shù)組中的第K個最大元素。」

具體鏈接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

示例?1:

輸入:?[3,2,1,5,6,4]?和?k?=?2
輸出:?5
示例?2:

輸入:?[3,2,3,1,2,4,5,5,6]?和?k?=?4
輸出:?4

經(jīng)典的TopK問題還有：最大（?。?K 個數(shù)、前 K 個高頻元素、第 K 個最大（?。┰?/p>

對此TopK問題本質(zhì)上是一個排序問題，排序算法一共有十個，這個還有很多排序算法沒有介紹過。

至于為什么TopK問題最佳的答案是堆排序？其實在空間和時間的復(fù)雜度來考量，雖說快排是最好的排序算法，但是對于100億個元素從大到小排序，然后輸出前 K 個元素值。

可是，無論我們掌握的是快速排序算法還是堆排序算法，在排序的時候，都需要將全部的元素讀入到內(nèi)存中。也就是說，100億個整型元素大約需要占用40GB的內(nèi)存空間，這聽起來就不像是普通民用電腦能干的事情，（一般的民用電腦內(nèi)存比這個小，比如我寫文章用的電腦內(nèi)存是 32GB）。

眾所周知，快速排序和堆排序的時間復(fù)雜度都可以達到，但是對于快速排序來說，數(shù)據(jù)是順序訪問的。而對于堆排序來說，數(shù)據(jù)是跳著訪問的。比如堆排序中，最重要的一個操作就是數(shù)據(jù)的堆化。因此，快速排序的時間復(fù)雜度是優(yōu)于堆排序的。

但是快速排序是新建數(shù)組，空間復(fù)雜度是，遠低于堆排序的。對于龐大的數(shù)據(jù)量，應(yīng)該優(yōu)先選擇堆排序。

如果使用heapq內(nèi)置模塊，尋找數(shù)組中的第K個最大元素就是一行代碼，heapq中的nlargest接口封裝好了，返回的是一個數(shù)組，需要切片取值。

import?heapq
class?Solution:
????def?findKthLargest(self,?nums:?List[int],?k:?int)?->?int:
????????return?heapq.nlargest(k,nums)[-1]

當(dāng)然，一般都是手寫堆排序，尋找數(shù)組中的第K個最大元素建立最小堆，尋找數(shù)組中的第K個最小元素建立最大堆，

思路：「取nums前K個元素建立大小為K的最小堆，后面就是維護一個容量為k的小頂堆，堆中的k個節(jié)點代表著當(dāng)前最大的k個元素，而堆頂顯然是這k個元素中的最小值?！?/strong>

因此只要遍歷整個數(shù)組，當(dāng)二叉堆大小等于K后，當(dāng)遇見大于堆頂數(shù)值的元素時彈出堆頂，并壓入該元素，持續(xù)維護最大的K個元素。遍歷結(jié)束后，堆頂元素即為第K個最大元素。時間復(fù)雜度。

class?Solution:
????def?findKthLargest(self,?nums:?List[int],?k:?int)?->?int:
????????heapsize=len(nums)
????????def?maxheap(a,i,length):
????????????l=2*i+1
????????????r=2*i+2
????????????large=i
????????????if?land?a[l]>a[large]:
????????????????large=l
????????????if?rand?a[r]>a[large]:
????????????????large=r
????????????if?large!=i:
????????????????a[large],a[i]=a[i],a[large]
????????????????maxheap(a,large,length)
????????????
????????def?buildheap(a,length):
????????????for?i?in?range(heapsize//2,-1,-1):
????????????????maxheap(a,i,length)

????????buildheap(nums,heapsize)
????????for?i?in?range(heapsize-1,heapsize-k,-1):
????????????nums[0],nums[i]=nums[i],nums[0]
????????????heapsize-=1
????????????maxheap(nums,0,heapsize)
????????return?nums[0]??

相反如果是求前k個最小，那么就用最大堆，因此面對TopK問題，最完美的解法是堆排序。因此，只有你看到數(shù)組的第K個……，馬上就是想到堆排序。

如果在數(shù)據(jù)規(guī)模小、對時間復(fù)雜度、空間復(fù)雜度要求不高的時候，真沒必要上 “高大上” 的算法，寫一個快排就很完美了。

TopK問題就像搜索引擎每天會接收大量的用戶搜索請求，它會把這些用戶輸入的搜索關(guān)鍵詞記錄下來，然后再離線地統(tǒng)計分析，得到最熱門的Top10搜索關(guān)鍵詞，啥啥惹事就出來了。

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點，歡迎 Star。

參考資料