0.13 堆

[215. 数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/?envType=study-plan-v2&envId=top-100-liked)
```py
import random
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        pivot = random.choice(nums)
        big, equal, small = [], [], []
        for num in nums:
            if num > pivot:
                big.append(num)
            elif num < pivot:
                small.append(num)
            else:
                equal.append(num)
        if len(big) >= k:
            return self.findKthLargest(big, k)
        if len(nums) - len(small) < k:
            return self.findKthLargest(small, k - (len(nums) - len(small)))
        return pivot
```
[347. 前 K 个高频元素](https://leetcode.cn/problems/top-k-frequent-elements/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        hash = {}
        for num in nums:
            hash[num] = hash.get(num,0) + 1
        heap = []
        for key, val in hash.items():
            if len(heap) < k:
                heapq.heappush(heap, (val,key))
            else:
                if val > heap[0][0]:
                    heapq.heappop(heap)
                    heapq.heappush(heap, (val, key))
        return [key for _, key in heap]
```
[295. 数据流的中位数](https://leetcode.cn/problems/find-median-from-data-stream/?envType=study-plan-v2&envId=top-100-liked)
```py
class MedianFinder:
    def __init__(self):
        self.heap_l = [] # 左区间最大值
        self.heap_r = [] # 右区间最小值

def addNum(self, num: int) -> None:
        if len(self.heap_l) == len(self.heap_r):
            heapq.heappush(self.heap_r, num)
            max_left = heapq.heappop(self.heap_r)
            heapq.heappush(self.heap_l, -max_left)
        else:
            heapq.heappush(self.heap_l, -num)
            min_right = - heapq.heappop(self.heap_l)
            heapq.heappush(self.heap_r, min_right)

def findMedian(self) -> float:
        if len(self.heap_l) == len(self.heap_r):
            return (-self.heap_l[0] + self.heap_r[0])/2
        else:
            return -self.heap_l[0]
```