为什么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

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