-1

我有一个数组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元素的负值，堆就会按预期排序。

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对数组元素进行排序但是当正值被推入堆时它不做任何事情。

4

1 回答 1

4

这被称为 the ，您可以在文档heap invariant中看到这一点以及它所说的：

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

请注意它说最小元素始终是根的地方，heap[0]这通过查看您的数据很明显。还要注意您的两个列表如何观察列出的属性heap[k] <= heap[2*k+1]以及heap[k] <= heap[2*k+2]所有 k。

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

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

如果您使用负数组，这同样适用。希望这有助于为您解决问题。

于 2020-01-04T14:43:11.077 回答