1

因此，我看到了各种帖子，其中用户在尝试从常规列表中进行堆放时会得到“不寻常/意外”的结果。(ex: Unusual result from heappop? ) 解决办法当然是先堆化它。

然而，对于这个LeetCode 解决方案， heapq 方法用于一个常规列表，该列表在使用这些方法之前没有被堆化，但仍然返回正确的预期结果。这是因为当您在常规列表中使用 heappop/heappush 时，它只会弹出/添加列表中的第一个元素？

4

2 回答 2

3

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

例子：

>>> 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
于 2021-01-05T19:34:12.580 回答
2

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

堆是数组，a[k] <= a[2*k+1]对于a[k] <= a[2*k+2]所有的k，从 0 开始计数元素。

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

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

对于具有 2 个或更多元素的列表，始终存在至少一个可能为假的条件，即a[0] <= a[1].

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

以下是每个的定义：

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随后仅通过调用heappopand进行修改heappush，因此在函数调用期间它仍然是一个堆。

于 2021-01-05T19:53:02.960 回答