python - 如何在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)

怎么做？

这是最小的元素。我想要 pop 最大的 emelment？

ps:这是题中的一部分find the max然后分成几个元素再放回堆中。

Answer 1

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)。