Python: 为什么堆第一次弹出不正确？

Question

我试图通过对列表的所有值取反来创建最大堆，但它似乎不起作用:

import heapq
x = range(1,10)
neg = [-n for n in x]
heapq.heappop(neg) # -1
heapq.heappop(neg) # -9
heapq.heappop(neg) # -8

但如果我这样做

heapq.heappop(x) # 1
heapq.heappop(x) # 2
heapq.heappop(x) # 3

它似乎工作正常。关于为什么 -1 返回的任何想法？

Answer 1

你不应该使用 heappush/heappop 除非你首先维护了堆不变性。

要从现有列表创建堆，请使用 heapq.heapify(mylist)。

>>> neg = [-n for n in range(1,10)]
>>> neg[0]  # peek
-1
>>> heapq.heapify(neg)
>>> neg[0]  # peek
-9
>>> -heapq.heappop(neg)  # largest element
9

Answer 2

heapq.heappop 对于最小堆仅；你不能只创建一个 maxheap 并期望基于 minheap 的函数在它上面工作，因为它不遵守 minheap 不变量。

如果目标是首先弹出 -9，您需要通过（有效地，O(n)）先堆化它来让您的堆支持适当的不变量：

heapq.heapify(neg)

之后您的代码将从 -9 下降到 -1。

如果您正在尝试最大堆，则不支持。 All the publically documented heapq functions work with minheaps（强调已添加）：

The API below differs from textbook heap algorithms in two aspects: (a) We use zero-based indexing. This makes the relationship between the index for a node and the indexes for its children slightly less obvious, but is more suitable since Python uses zero-based indexing. (b) 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).

模块中有一些选定的（未记录的）基于 maxheap 的函数可以使用，例如heapq._heappop_max，但它们不是 API 的记录部分，并且可能随时更改或消失。

Python: 为什么堆第一次弹出不正确？

Python: Why does heap give incorrect first pop?

python

heap