为什么heapq使用列表的前面？

Question

我正在使用python的heapq实现。我理解它的功能，但我不明白为什么它使用列表的前面而不是后面来存储最小的元素？考虑到在列表开始时改变元素的成本，我本以为这会很慢

有谁能澄清为什么heapq使用列表的最前面，以及为什么这不会导致它变慢

>>> import heapq
>>> A = [10,3,5,2,1,3,5]
>>> heapq.heapify(A)
>>> A
[1, 2, 3, 10, 3, 5, 5]
>>> heapq.heappop(A)
1
>>> A
[2, 3, 3, 10, 5, 5]

Answer 1

heapq的要点是使用一个heap结构——一个二进制堆，具体来说，其中每个节点小于或等于其所有子节点。pop operation总是围绕O（logn）元素移动，因此从这个意义上讲，列表的顺序并不重要（它不像.pop(0)，它会移动O（n）元素–请注意，在操作之后，列表是如何[2, 3, 3, 10, 5, 5]，而不是[2, 3, 10, 3, 5, 5]）。剩下的考虑只是使树结构易于从列表中生成，这是通过最简单的方式实现的，在开始时有根，其中索引i处的每个节点的子节点都在索引2i+1和2i+2处

Answer 2

heappop不会从列表的前面弹出。它从列表的后面弹出，然后用最后一项替换第一项并进行筛选。除了筛选之外，堆没有质量转移，这是必需的

Answer 3

heappop正在使用最后一个元素。它调用_siftup，并在位置-1处弹出元素（请参见：heap.pop()）。如果仔细观察，它将返回returnitem中所述的第一个元素作为返回值，但它不会弹出此项或在算法中使用此值

heapq.py：

def heappop(heap):
    """Pop the smallest item off the heap, maintaining the heap invariant."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        _siftup(heap, 0)
        return returnitem
    return lastelt

参考资料

CPython heapq:https://github.com/python/cpython/blob/v3.8.5/Lib/heapq.py#L135-L143