VSCode Python heap[0] 修改堆项后不再是 min

Question

在 VS Code 中，我有一个 Python 堆变量，它是一个三项元组的列表，定义为

heapq.heappush(heap, (len(candidates[(i, j)]), i, j))

在调试开始时，

heap[0]

始终是

len(candidates[i, j])

最短的元组。然而，经过几轮修改堆中的项目后 -

heap.remove((length, r, c))
heapq.heappush(heap, (length - 1, r, c))

、

heap[0]

不再指向最小项目。例如，在调试控制台中，

heap[0]

可能会显示

(3, 4, 5)

，而存在另一个堆项

(1, 6, 7)

。因为

1 < 3

，显然

(3, 4, 5)

不应该位于堆中其他项目之上。

Answer 1

它不再指向最小项，因为在执行

remove()

之后，您拥有的数据结构不再是堆。 从技术上讲，Python 允许您对某些值

list.remove(x)

执行

x

，但堆的全部意义在于 仅 让您

(heap)pop

或“删除”堆中的最低值。

这样做

heap.remove()

在逻辑上是不正确的，并且将不再保持堆不变性。使用

heapq.heappop(heap)

从堆中删除元素。