python中利用heapq实现优先队列（priority _queue）

在LeetCode第232次周赛中，题目很适合用优先队列，但是之前以为仅有C++中有优先队列，因此比赛中采用了二分查找的方式进行解答，不过超时了。

堆的基础是一个表明完全二叉树的数组，并且堆中的各个元素可以进行比较，从而可以通过各个元素之间的比较确定元素在一个完全二叉树中的哪一层。

heapq是python中实现堆操作的模块，heapq中有一系列函数，可以对一个list进行操作，即可实现模拟一个小顶堆。list中元素只要相互之间可以进行比较，那么就可以堆此list进行heapq中的操作，list中元素不仅可以为int、float、str等显然可以比较的类型，也可以是turple、list等不太显然但是的确 可以比较的类型，例如有如下代码，建立一个小顶堆，乱序插入一系列list并在heapify后全部pop出，代码如下：

minHeap = []
minHeap.append([1, 5])
minHeap.append([1, 1])
minHeap.append([1, 2])
minHeap.append([1, 4])
minHeap.append([1, 3])
heapify(minHeap)
while len(minHeap) != 0:
    print(heappop(minHeap))

代码执行结果如下：

[1, 1]
[1, 2]
[1, 3]
[1, 4]
[1, 5]

可见，在pop时，各个元素类型为list，以从小到大的次序被pop出。

如果我们有这样一个需求，建立一个堆，令堆以数值a作为排列的根据，并且还希望记录与a对应的数值b和c，那么我们可以令堆中的每个元素都为[a,b,c]这种形式，此时heapq中操作执行时即直接比较类型为list的各个元素。

以此题为例，https://leetcode-cn.com/problems/maximum-average-pass-ratio/，我们需要建立一个大顶堆maxHeap，从而每次可以获得增加一个学生提升最大的班级，每次将一个机智学生插入班级时，heappop出增加一人可获得最大提升的班级，并将此班级处理后重新heappush入maxHeap，代码如下：

class Solution:

    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        def diff(x, y): return (x+1)/(y+1)-x/y#增加一个学生能够提升的数值
        maxHeap = list()#建立大顶堆，注意heapq默认处理小顶堆
        for each in classes:#堆中的每个元素为一个list，每个元素分别为能够提升的数值，已通过数，总数
            heappush(maxHeap, [-diff(each[0], each[1]), each[0], each[1]])
        # print(maxHeap)
        for _ in range(extraStudents):
            _, x, y = heappop(maxHeap)
            heappush(maxHeap, [-diff(x+1, y+1), x+1, y+1])#已通过数、总数各加一，并计算新的diff
        res = 0
        for each in maxHeap:#依次统计通过率，并给出结果
            res += each[1]/each[2]

        return res/len(classes)

Leetcode中同样用到优先队列的题目：
https://leetcode-cn.com/problems/k-th-smallest-prime-fraction/
https://leetcode-cn.com/problems/maximum-number-of-eaten-apples/submissions/
https://leetcode-cn.com/problems/maximum-frequency-stack/

2021.4.18 补充，当日周赛T3也是典型的优先队列