python, heapq: heappushpop() 和 heapreplace() 的区别

Question

当我测试以下代码时，我无法弄清楚函数 heapq.heappushpop() 和 heapq.heapreplace() 之间的区别（除了 push/pop 操作的序数）。

>>> from heapq import *
>>> a=[2,7,4,0,8,12,14,13,10,3,4]
>>> heapify(a)
>>> heappush(a,9)
>>> a
[0, 2, 4, 7, 3, 9, 14, 13, 10, 8, 4, 12]
>>> heappop(a)
0
>>> b=a.copy()
>>> heappushpop(a,6)
2
>>> heapreplace(b,6)
2
>>> a
[3, 4, 4, 7, 6, 9, 14, 13, 10, 8, 12]
>>> b
[3, 4, 4, 7, 6, 9, 14, 13, 10, 8, 12]

Answer 1

在许多常见情况下，最终结果似乎相同，但过程和行为不同，并且在极端情况下可见：

heappushpop() 相当于先推送，然后弹出，这意味着，除其他外，您的堆大小可能会在此过程中发生变化（并且，例如，如果您的堆为空，您将得到返回您推送的元素）。

heapreplace() 相当于先出栈，再入栈，额外的限制是保证你的堆大小在这个过程中不会改变。这意味着您将在空堆上遇到错误，以及其他有趣的角落行为。

Answer 2

heapreplace(a, x) returns原本在a中的最小值而不管x的值，而顾名思义，heappushpop(a, x)推x 到 a 之前弹出最小值。使用您的数据，这是一个显示差异的序列：

>>> from heapq import *
>>> a = [2,7,4,0,8,12,14,13,10,3,4]
>>> heapify(a)
>>> b = a[:]
>>> heappushpop(a, -1)
-1
>>> heapreplace(b, -1)
0

Answer 3

了解 heapq 拥有这些方法的原因是 提高效率
非常重要在功能方面，你可以这样想

# if we assume len(list) == k
heapq.heappushpop(list, elem): # 2*log(K) runtime
  heapq.push(list, elem)  # log(K) runtime
  return heapq.pop(list)  # log(k) runtime

heapq.heapreplace(list, elem): # 2*log(K) runtime
  returnValue = heapq.pop(list) # log(K) runtime
  heapq.push(list, elem)        # log(K) runtime
  return returnValue

但是，当您可以使用 push、pop 完成所有操作时，为什么还要有两个附加功能？ heapq.heappushpop() 和 heapq.heapreplace() 仅使用 log(K) 时间！

# if we assume len(list) == k
heapq.heappushpop(list, elem):         # log(K) runtime
  if elem < list[0]:
      return elem
  return heapq.heapreplace(list, elem) # log(K) runtime

heapq.heapreplace(list, elem):  # log(K) runtime
  returnValue = list[0]         # peek operation
  list[0] = elem
  heapq.bubbledown(list,0)      # restore heap structure in log(K) time
  return returnValue

耗时操作是heapq.bubbledown（实际上不是pythonapi），在hood下，这个函数与[=21=非常相似]

您会注意到这些函数在解决 Merge K sorted arrays 等问题时非常方便。如果你只使用 pop + push（比如 java），它会慢两倍 :(

Answer 4

heapq.heappushpop相当于先push再pop

而

heapq.heapreplace等同于先pop再push

作为演示：

>>> seq
[0, 1, 5, 2, 6, 7, 9, 3]
>>> heapq.heappushpop(seq, -1)
-1
>>> seq
[0, 1, 5, 2, 6, 7, 9, 3]
>>> heapq.heapreplace(seq, -1)
0
>>> seq
[-1, 1, 5, 2, 6, 7, 9, 3]

python, heapq: heappushpop() 和 heapreplace() 的区别

python, heapq: difference between heappushpop() and heapreplace()

python

heap