保持固定大小的堆-python

Question

h = []
heapq.heappush(h,(10, 1200))
heapq.heappush(h,(20, 31))
heapq.heappush(h,(5, 1))

我想保持一个固定的堆大小，比如说3，所以当我下一次有heapq.heappush(h,(3,15))时，值为20的键被删除，剩下的值是3、5和10。有什么办法吗？

Answer 1

没有内置的heapq来检查大小，所以您必须自己检查：

if len(h) < capacity:
    heapq.heappush(h, thing)
else:
    # Equivalent to a push, then a pop, but faster
    spilled_value = heapq.heappushpop(h, thing)
    do_whatever_with(spilled_value)

另外，注意heapq实现的是最小堆，而不是最大堆。你需要颠倒你的优先顺序，可能是通过否定它们。

Answer 2

我发现这篇文章我试图实现一个固定大小的top-n堆，下面是我可以提供的解决方案：

from heapq import heapify, heappush, heappushpop

class MaxHeap():
    def __init__(self, top_n):
        self.h = []
        self.length = top_n
        heapify( self.h)

    def add(self, element):
        if len(self.h) < self.length:
            heappush(self.h, element)
        else:
            heappushpop(self.h, element)

    def getTop(self):
        return sorted(self.h, reverse=True)