代码之家 › 专栏 › 技术社区 › user504909

如何在python中获得最大堆

max-heap heap python

13

user504909 · 技术社区 · 8 年前

我在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)

怎么做?

哪个是最小的元素。我要最大的药水?

ps:这是问题的一部分,找到最大值,然后分成几个元素,然后将其放回堆中。

2 回复 | 直到 8 年前

1

16

Rory Daulton 8 年前

我们的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) 在负堆中检查最大的项。

2

6

Niema Moshiri 8 年前

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