python的堆队列（优先队列）

写在前面

最近在刷算法题，所以记录一些算法权当加深记忆。
heapq这个模块之前是读过源码还写过解析的，用起来却是啥也不记得（o(╥﹏╥)o），所以还是不能读死书，要学以致用才行呀。

关于堆（python实现是最小堆）

首先是个二叉树，特性是根节点（堆顶）总是最小的元素，即heap[0]。

常用的方法

• heapify(x: List())
• heappush(heap: List(), item)
• heappop(heap: List(), item)

上面三个不用讲。

• heapreplace(heap: List(), item)
• heappushpop(heap: List(), item)

这两个都比heappush+heappop的组合快，因为heapreplace直接把新元素放在堆顶下沉，heappushpop则是先判断再决定是否下沉，讲得可能不是很清楚因为需要懂push和pop的实现，不然就不用管直接用吧。

• merge(*iterables, key=None, reverse=False)

用于你不想合成一个堆，但又要看作一个堆的情况。

• nsmallest和nlargest

内部优化对n的大小会有不同的方法，比如min(n=1),sort(n=len),heapreplace。

实战

维护第k大的值

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.heap = []
        self.k = k
        for i in nums:
            self.add(i)

    def add(self, val: int) -> int:
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        else:
            if val > self.heap[0]:
                heapq.heapreplace(self.heap, val)
        return self.heap[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15