如何在Python中获取最大堆

Question

我在Python中使用了heapq模块，发现无论我是否使用reverse=True，我只能获得最小堆。

即使我使用了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)

如何做？

哪个是最小的元素。我想弹出最大的元素？

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

- user504909

---

nlargest(h, 1)? - cs95

@cᴏʟᴅsᴘᴇᴇᴅ 那只是一种不好的编写 max(h) 的方式。 - Stefan Pochmann

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

- Rory Daulton

---

我不理解你关于nlargest的说法。为了找到您所提供的可迭代对象的最大元素，它需要O(n)的时间，而不是O(log(n))。 - Stefan Pochmann

实际上，根据文档，我认为它实际上是O(n log n)：“等同于：sorted(iterable, key=key, reverse=True)[:n]” - Niema Moshiri

@NiemaMoshiri 这意味着相同的结果，而不是相同的复杂度。顺便说一下，你刚才说询问前n个最大元素的时间复杂度为O(0)。 - Stefan Pochmann

啊，我不知道它只意味着输出是等价的，而不是时间复杂度。谢谢你！另外，我不确定你说的O(0)时间是什么意思。大O时间复杂度是描述随着n趋近于无穷大时渐进运行时间可扩展性的一种方式；你不能直接插入一个n的值。 - Niema Moshiri

@NiemaMoshiri 我当然可以插入一个n的值。大O复杂度是一个“对于所有n≥n₀的语句”。所以对于n=n₀也是成立的。我可以插入那个值。你没有说你想要什么n₀，所以我假设n=1，因为我们正在讨论如何找到最大的第1个值。但这并不重要。无论你的n₀是多少，我只需要选择n=n₀，然后O(n log n) = O(n₀ log n₀) = O(1)。你仍然说它是常数时间，这是错误的。 - Stefan Pochmann

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

- Niema Moshiri

---

pq 没有弹出函数。 - user504909

不确定您的意思。PriorityQueue 的 get() 函数相当于堆的 pop()：它会移除并返回最高优先级的元素。 - Niema Moshiri

抱歉，我之前误以为会删除最高优先级的元素。感谢您指出。 - user504909

我可以使用索引轻松获取第二大的数字。 - user504909

如何呢？在最大堆中，根是最大的元素（所以你可以确保最大的元素在索引0），但是第二大的元素可以是根的任一子节点（因此它可以在索引1或索引2中）。如果您确定您每次只想要最大的2个元素，那么我同意您可以有效地这样做：h [0]用于最大值，max(h[1], h [2])用于次大值。 - Niema Moshiri

值得注意的是，PriorityQueue具有同步方法，因此会产生一些线程开销。 - Ryhan