上次介紹了堆排序，這次介紹堆排序常見的應用場景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:
returnheapq.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 la[large]:
large=l
if ra[large]:
large=r
if large!=i:
a[large],a[i]=a[i],a[large]
maxheap(a,large,length)
def buildheap(a,length):
foriinrange(heapsize//2,-1,-1):
maxheap(a,i,length)
buildheap(nums,heapsize)
foriinrange(heapsize-1,heapsize-k,-1):
nums[0],nums[i]=nums[i],nums[0]
heapsize-=1
maxheap(nums,0,heapsize)
returnnums[0]
相反如果是求前k個最小，那麼就用最大堆，是以面對TopK問題，最完美的解法是堆排序。是以，隻有你看到數組的第K個……，馬上就是想到堆排序。
如果在資料規模小、對時間複雜度、空間複雜度要求不高的時候，真沒必要上 “高大上” 的算法，寫一個快排就很完美了。
TopK問題就像搜尋引擎每天會接收大量的使用者搜尋請求，它會把這些使用者輸入的搜尋關鍵詞記錄下來，然後再離線地統計分析，得到最熱門的Top10搜尋關鍵詞，啥啥惹事就出來了。
本文已收錄 GitHub https://github.com/MaoliRUNsen/runsenlearnpy100
【編輯推薦】
【責任編輯：姜華 TEL：(010)68476606】
點贊 0