3 优先队列

在 C++ 中有所谓的std::priority_queue模版，其底层逻辑就是堆。在 python 中也有对应的heapq模块，但是是阉割版，只能维护小顶堆。

heapq 模块介绍¶

首先，这个模块在蓝桥杯里是可以直接导入的，放行用。首先创建一个列表，可以使用heapq.heapify()方法直接把列表变成小顶堆。

heap = [2, 3, 1, 4]
heapq.heapify(heap)
print(heap) # [1, 3, 2, 4]

经典的操作包括弹出堆头并返回heappop、往堆中追加heappush等。
heapq模块甚至包装了nsmallest和nlargest方法。我觉得这些方法在算法比赛中没有啥适用性，主要是时间复杂度的问题。nsmallest(k)还好，估计是 $O(k\log n)$。nlargest相当麻烦，我觉得难逃 $O(n\log n)$。
还有heappushpop，heapreplace这样的方法，感觉没必要去记哈。

PriorityQueue 类¶

Python 中还存在这样的一个类，它在功能上可以完全实现优先队列（其实heapq稍加改造也可以完全实现优先队列，但既然不能直接拿来用的话，还不如手搓堆）。在蓝桥杯环境中也可以导入这个模块：

from queue import PriorityQueue

这个类是专门为多线程环境设计的，因此会存在锁开销；但是他可以指定优先级，从而实现大顶堆、小顶堆或者其他类型的优先队列。

from queue import PriorityQueue
q = PriorityQueue()
q.put((2, 'code'))
q.put((1, 'eat'))
q.put((3, 'sleep'))
while not q.empty():
    next_item = q.get()
    print(next_item)
# 结果：
#   (1, 'eat')
#   (2, 'code')
#   (3, 'sleep')

这个例子中，put()所接受的是一个二元组，二元组的第一个元素指定优先级，第二个元素可以用来存储实际的数据。

实际上put()也可以接受三元组来着，我测试了之后，发现如果给put()传入 $n$ 元组，那么前 $n-1$ 个会作为优先级，最后一个会作为数据。而前 $n-1$ 元素所组成的优先级又是从前往后一一比对的，比如 $n=3$ 的情况下，$(1,3)$ 会比 $(2,-1)$ 优先级更低一些，因为 $1<2$。
但是大多数情况下一个优先级参数就足够了，所以最好还是用二元组。

经过简单包装，可以实现一个极简的优先队列的模版：

from queue import PriorityQueue
class pQueue:
    def __init__(self, reverse=False, key=None):
        self.q = PriorityQueue()
        transfer = key if key is not None else lambda x:x
        if reverse:
            self.transfer = lambda x:-transfer(x)
        else:
            self.transfer = transfer
    def put(self, value):
        self.q.put((self.transfer(value), value))
    def empty(self):
        return self.q.empty()
    def get(self):
        return self.q.get()[1]

例如，实现大顶堆：

q = pQueue(reverse=True)
q.put(114)
q.put(514)
q.put(1919)
while(not q.empty()):
    print(q.get(),end=' ')
# 1919 514 114

或者按照一些其他的元素排序，比如堆里面的元素是平面点 $(x _ i,y _ i)$，构成基于横坐标的大顶堆：

q = pQueue(reverse=True, key=lambda x:x[0])
q.put((1,-1))
q.put((5,-2))
q.put((3,7))
while(not q.empty()):
    print(q.get(),end=' ')
# (5, -2) (3, 7) (1, -1)

手写堆¶

Python 这门语言设计之初就不是为了执行效率，而是为了简单上手的语法和接口。所以上面这两个堆实际的时间开销难以估计。如果想要求更快，完全可以自己手写一个堆，这样时间复杂度是透明的。当然这样会花费更多的时间，赛场上全靠自己权衡。