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

「@Author：Runsen」

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

利用堆求TopK問題

TopK問題是一個堆排序典型的應用場景。

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

對標的是Leetcode第215題：「數組中的第K個最大元素。」

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

在未排序的數組中找到第 k 個最大的元素。請注意，你需要找的是數組排序後的第 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
經典的TopK問題還有：最大（小） K 個數、前 K 個高頻元素、第 K 個最大（小）元素
對此TopK問題本質上是一個排序問題，排序算法一共有十個，這個還有很多排序算法沒有介紹過。
至於為什麼TopK問題最佳的答案是堆排序？其實在空間和時間的複雜度來考量，雖說快排是最好的排序算法，但是對於100億個元素從大到小排序，然後輸出前 K 個元素值。
可是，無論我們掌握的是快速排序算法還是堆排序算法，在排序的時候，都需要將全部的元素讀入到內存中。也就是說，100億個整型元素大約需要佔用40GB的內存空間，這聽起來就不像是普通民用電腦能幹的事情，（一般的民用電腦內存比這個小，比如我寫文章用的電腦內存是 32GB）。
眾所周知，快速排序和堆排序的時間複雜度都可以達到
但是快速排序是新建數組，空間複雜度是
如果使用heapq內置模塊，尋找數組中的第K個最大元素就是一行代碼，heapq中的nlargest接口封裝好了，返回的是一個數組，需要切片取值。
import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k,nums)[-1]
當然，一般都是手寫堆排序，尋找數組中的第K個最大元素建立最小堆，尋找數組中的第K個最小元素建立最大堆，
思路：「取nums前K個元素建立大小為K的最小堆，後面就是維護一個容量為k的小頂堆，堆中的k個節點代表著當前最大的k個元素，而堆頂顯然是這k個元素中的最小值。」
因此只要遍歷整個數組，當二叉堆大小等於K後，當遇見大於堆頂數值的元素時彈出堆頂，並壓入該元素，持續維護最大的K個元素。遍歷結束後，堆頂元素即為第K個最大元素。時間複雜度
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 l<length and a[l]>a[large]:
                large=l
            if r<length and 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問題，最完美的解法是堆排序。因此，只有你看到數組的第K個……，馬上就是想到堆排序。
如果在數據規模小、對時間複雜度、空間複雜度要求不高的時候，真沒必要上 「高大上」 的算法，寫一個快排就很完美了。
TopK問題就像搜尋引擎每天會接收大量的用戶搜索請求，它會把這些用戶輸入的搜索關鍵詞記錄下來，然後再離線地統計分析，得到最熱門的Top10搜索關鍵詞，啥啥惹事就出來了。
本文已收錄 GitHub，傳送門~[1] ，裡面更有大廠面試完整考點，歡迎 Star。
參考資料[1]
傳送門~: https://github.com/MaoliRUNsen/runsenlearnpy100