python 中的 heappush 行为

Question

我有一个数组 arr = [1,2,1,3].

当我使用 heappush 函数将数组元素按原样推入堆中时，顺序与数组中的顺序完全相同：

arr = [1,2,1,3]
heap = []
for i in range(len(arr)):
    heapq.heappush(heap, arr[i])
print(heap)

Result: [1, 2, 1, 3]

现在，如果我压入 arr 元素的 negative 值，堆将变为 sorted 因为它应该是。

arr = [1,2,1,3]
heap = []
for i in range(len(arr)):
     heapq.heappush(heap,  - arr[i])    <---- Here
print(heap)

Result: [-3, -2, -1, -1]

我想知道为什么 heappush 在将数组元素的负值添加到堆中时对数组元素进行排序，但在将正值推入堆中时却不执行任何操作。

Answer 1

这被称为 heap invariant，您可以在 docs 中看到它的声明，以及它说的地方：

堆是二叉树，其中每个父节点的值都小于或等于它的任何子节点。此实现使用数组，其中 heap[k] <= heap[2*k+1] 和 heap[k] <= heap[2*k+2] 用于所有 k，从零开始计算元素。为了便于比较，不存在的元素被认为是无限的。堆的有趣属性是它的 最小元素始终是根，堆 [0].

请注意其中所说的最小元素始终是根，heap[0]，这通过查看您的数据很明显。还要注意你的两个列表如何观察所有 k.

列出的 heap[k] <= heap[2*k+1] 和 heap[k] <= heap[2*k+2] 的属性

现在，如果我们查看您的列表，我们可以看到观察到的属性：

inf = float('inf')
arr = [1, 2, 1, 3]

for i in range(len(arr)):
    x = arr[i]
    try:
        y = arr[2 * i + 1]
    except IndexError:
        y = inf
    print('x <= y is {}'.format(x <= y))

x <= y is True
x <= y is True
x <= y is True
x <= y is True

如果使用负数组，同样适用。希望能帮助您解决问题。

python 中的 heappush 行为

heappush behavior in python

python

heap

heapq