堆排序怎么解決TopK問題

本篇內(nèi)容主要講解“堆排序怎么解決TopK問題”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“堆排序怎么解決TopK問題”吧!

在未排序的數(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 個最大(小)元素

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

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

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

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

但是快速排序是新建數(shù)組，空間復雜度是，遠低于堆排序的。對于龐大的數(shù)據(jù)量，應該優(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]

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

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

因此只要遍歷整個數(shù)組，當二叉堆大小等于K后，當遇見大于堆頂數(shù)值的元素時彈出堆頂，并壓入該元素，持續(xù)維護最大的K個元素。遍歷結(jié)束后，堆頂元素即為第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問題，最完美的解法是堆排序。因此，只有你看到數(shù)組的第K個……，馬上就是想到堆排序。

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

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

到此，相信大家對“堆排序怎么解決TopK問題”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學習！