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

但如果我这么做了

^{pr2}$

它似乎工作正常。你知道为什么-1会回来吗？在

Answer 1

heapq.heappop仅对minheap是的；您不能只创建maxheap并期望基于minheap的函数在其上工作，因为它不观察minheap不变量。在

如果目标是首先弹出-9，则需要通过（有效地，O(n)）首先对堆进行堆处理，使堆支持适当的不变量：

heapq.heapify(neg)

之后，您的代码将从-9跳到-1。在

如果您正在尝试使用maxheap，则不支持该操作。All the publically documented ^{} 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的文档部分，随时可能更改或消失。在

Answer 2

除非首先维护了堆不变量，否则不应使用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