带有常规列表的 Heapop 和 Heappush（非堆化列表）

Question

所以我看过很多帖子，用户在尝试从常规列表中 heappop 时得到“unusual/unexpected”结果。 (ex: ) 解决方案当然是先堆化它。

但是，为此 LeetCode solution heapq 方法用于常规列表，该列表在使用这些方法之前未堆化，但仍然 return 正确的预期结果。这是因为当您在常规列表中使用 heappop/heappush 时，它只是 pops/adds 列表中的第一个元素吗？

Answer 1

在示例中，他们在最初包含单个元素（源）的列表上使用 heappop，因此它满足堆属性。
在使用 heappop 或 heappush 等函数之前，不必在列表上使用 heapify。事实上，该列表可能为空，包含单个元素，或者是一个已经满足堆属性.

的列表

示例：

>>> l = [1, 3, 2, 5, 4] # initial list that respects the heap property
>>> heappop(l)
1
>>> heappop(l)
2
>>> heappop(l)
3
>>> heappop(l)
4
>>> heappop(l)
5

Answer 2

heapq 模块没有定义任何新的数据类型来表示堆。堆只是一个列表（或者实际上是任何序列），它遵循 heap invariant:

Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for all k, counting elements from 0.

为了使列表不是堆，找到不变量为假的索引k 是必要且充分的。

这对于空列表和单项列表是不可能的，因为所需的列表元素根本不存在，所以两者都是普通的堆。

对于包含 2 个或更多元素的列表，总是至少有一个条件可以为假，即 a[0] <= a[1]。

heappush 和 heappop 都被记录为“保持堆不变性”：如果每个函数的第一个参数在函数被调用之前是一个堆，那么在函数 [= 之后它仍然是一个堆56=]。（如果第一个参数不是堆，它们的行为本质上是未定义的。）

以下是每个的定义：

def heappush(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown(heap, 0, len(heap)-1)

私有函数 _siftdown 负责在附加后恢复堆不变量 item 可能会违反它。

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

私有函数_siftup负责在将heap[0]替换为lastelt后恢复堆不变量可能违反了它。

在您链接的代码中，pq 被初始化为一个单项列表，正如我们之前提到的，它已经是一个堆。由于 pq 随后仅通过调用 heappop 和 heappush 进行修改，因此在函数调用期间它仍然是一个堆。

带有常规列表的 Heapop 和 Heappush（非堆化列表）

Heapop and Heappush with a regular list (non-heapified list)

python

heapq