首先認識堆：
1、認識python3中關(guān)于堆的函數(shù)
1）heapq.heapify可以原地把一個list調(diào)整成堆[小頂堆] 而 heapq.nlargest 會調(diào)成大頂堆
2）heapq.heappop可以彈出堆頂罗标，并重新調(diào)整
3）heapq.heappush可以新增元素到堆中，不會調(diào)整
4）heapq.heapreplace可以替換堆頂元素，并調(diào)整下
5）為了維持為K的大小次舌，初始化的時候可能需要刪減伊约，后面需要做處理就是如果不滿K個就新增姚淆，否則做替換；
6）heapq其實是對一個list做原地的處理屡律，第一個元素就是最小的腌逢，直接返回就是最小的值
1、最小的k個數(shù)
輸入整數(shù)數(shù)組 arr 超埋，找出其中最小的 k 個數(shù)搏讶。例如，輸入4霍殴、5媒惕、1、6来庭、2妒蔚、7、3月弛、8這8個數(shù)字肴盏，則最小的4個數(shù)字是1、2帽衙、3菜皂、4。
示例 1：
輸入：arr = [3,2,1], k = 2
輸出：[1,2] 或者 [2,1]
示例 2：
輸入：arr = [0,1,2,1], k = 1
輸出：[0]
關(guān)鍵點
1佛寿、取負值幌墓，建最小堆，實質(zhì)上是最小的K個數(shù)（堆頂取正值后最大）
2冀泻、遍歷剩下的元素，維護這個最小堆蜡饵，關(guān)鍵數(shù)判斷值與堆頂元素的關(guān)系弹渔，如果值大于堆頂元素，要加入堆
代碼如下：
class?Solution:
????def?getLeastNumbers(self,?arr:?List[int],?k:?int)?->?List[int]:
????????if?k?==?0:
????????????return?list()
????????tmp=[-x?for?x?in?arr[:k]]
????????heapq.heapify(tmp)
????????#最小堆溯祸，最頂最小肢专，實質(zhì)上是最小的k個數(shù)
????????for?i?in?range(k,?len(arr)):
????????????if?tmp[0]?<?-arr[i]:
????????????????heapq.heappop(tmp)
????????????????heapq.heappush(tmp,?-arr[i])
????????return?[-x?for?x?in?tmp]
？焦辅？博杖？利用最大堆如何實現(xiàn)？筷登？剃根？
2、數(shù)據(jù)流中第K大元素
設計一個找到數(shù)據(jù)流中第K大元素的類（class）前方。注意是排序后的第K大元素狈醉，不是第K個不同的元素廉油。
你的?KthLargest?類需要一個同時接收整數(shù)?k 和整數(shù)數(shù)組nums?的構(gòu)造器，它包含數(shù)據(jù)流中的初始元素苗傅。每次調(diào)用?KthLargest.add抒线，返回當前數(shù)據(jù)流中第K大的元素。
示例:
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);? ?// returns 4
kthLargest.add(5);? ?// returns 5
kthLargest.add(10);? // returns 5
kthLargest.add(9);? ?// returns 8
kthLargest.add(4);? ?// returns 8
說明:
你可以假設?nums?的長度≥?k-1?且k ≥?1渣慕。
關(guān)鍵點
1嘶炭、使用最小堆，得到第K個大的數(shù)逊桦，構(gòu)建k個值的最小堆
2旱物、判斷值于堆頂元素的關(guān)系，如果值大于堆頂元素卫袒，插入并重新調(diào)整宵呛，返回堆頂元素
代碼如下：
from?heapq?import?*
class?KthLargest:
????def?__init__(self,?k:?int,?nums:?List[int]):
????????self.k?=?k
????????self.nums?=?nums
????????heapify(self.nums)
????????while?len(self.nums)>self.k:?#cut?heap?to?size:k
????????????heappop(self.nums)
????def?add(self,?val):
????????"""
????????:type?val:?int
????????:rtype:?int
????????"""
????????if?len(self.nums)?<?self.k:
????????????heappush(self.nums,?val)
????????????heapify(self.nums)?#cation
????????else:
????????????top?=?float('-inf')
????????????if?len(self.nums)?>?0:
????????????????top?=?self.nums[0]
????????????if?top?<?val:
????????????????heapreplace(self.nums,?val)
????????????????#替換堆頂元素，病調(diào)整下
????????return?self.nums[0]
參考資料：
1夕凝、python實現(xiàn)最大堆宝穗，最小堆和堆排序https://blog.csdn.net/qq_40587575/article/details/89290135#0.%E4%BB%80%E4%B9%88%E6%98%AF%E5%A0%86
2、Python的heapq的文檔
