如何在python中获得最大堆

The documentation 说,

我们的pop方法返回最小的项,而不是最大的项(称为 教科书中的“最小堆”;最大堆在文本中更常见,因为 其是否适合就地分拣)。

因此,无法直接获得最大堆。然而,间接获得它的一种方法是推动 消极的 ,然后在弹出项目后再次取负数。因此 heappush(h, (200, 1)) 您执行 heappush(h, (-200, -1)) . 要弹出并打印max项目,请执行

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

有其他方法可以获得相同的效果,具体取决于您在堆中存储的内容。

请注意,正在尝试 h[-1] 在最小堆中,无法找到最大项—堆定义不能保证最大项将位于列表的末尾。 nlargest 应该可以工作,但时间复杂度为 O(log(n)) 只检查最小堆中最大的项,这违背了堆的目的。我的方式具有时间复杂性 O(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