如何在python中获取最大堆

Question

我在python中使用heapq模块,我发现我只能使用min heap,即使我使用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)

怎么做？

这是最小的元素.我想要流行最大的emelment？

ps:这是问题的一部分找到max然后分成几个元素然后把它放回堆中.

Answer 1

文件说,

我们的pop方法返回最小的项目,而不是最大的项目(在教科书中称为"最小堆";"最大堆"在文本中更常见,因为它适用于就地排序).

所以你无法直接获得最大堆.但是,间接获取它的一种方法是在堆上推送项目的负数,然后在弹出项目后再次取消负数.而不是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)在负堆中有时间复杂度来检查最大的项目.

Answer 2

为什么不使用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