如何在python中获取最大堆

Question

我在python中使用heapq模块，我发现我只能使用最小堆，即使我使用reverse=True

我还是有最小的顶堆

from heapq import *

h=[]
merge(h,key=lambda e:e[0],reverse=True)
heappush(h, (200, 1))
heappush(h, (300,2))
heappush(h, (400,3))
print(heappop(h))

我仍然得到结果：

(200, 1)

我想得到结果：

(400,3)

怎么做？

这是最小的元素。我要波普最大的催吐剂？

注：这是问题的一部分，找到最大值，然后分成几个元素，然后放回堆中。

Answer 1

为什么不使用PriorityQueue对象？您可以存储(priority,key)元组。创建最大堆的一个简单解决方案是使priority与key相反：

from Queue import PriorityQueue
pq = PriorityQueue()
for i in range(10): # add 0-9 with priority = -key
    pq.put((-i,i))
print(pq.get()[1]) # 9

Answer 2

The documentation说

Our pop method returns the smallest item, not the largest (called a “min heap” in textbooks; a “max heap” is more common in texts because of its suitability for in-place sorting).

所以你不能直接得到最大堆。但是，一种间接获取它的方法是将项的负推到堆上，然后在弹出项后再次获取负。因此，不是heappush(h, (200, 1))，而是执行heappush(h, (-200, -1))。要弹出并打印最大项，请执行

negmaxitem = heappop(h)
maxitem = (-negmaxitem[0], -negmaxitem[1])
print(maxitem)

有其他方法可以获得相同的效果，这取决于您到底在堆中存储了什么。

请注意，在最小堆中尝试h[-1]无法找到最大项——堆定义不能保证最大项最终会出现在列表的末尾。nlargest应该可以工作，但时间复杂度为O(log(n))，只需检查最小堆中最大的项，这就破坏了堆的目的。我的方法在负堆中有时间复杂度O(1)来检查最大的项。