python、heapq：heappushpop() 和 heapreplace() 之间的区别

Question

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

>>> 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

无论

heapreplace(a, x)

的值如何，

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 2

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

heappushpop()

相当于先推入，然后弹出，这意味着您的堆大小可能会在此过程中发生变化（例如，如果您的堆为空，您将取回您推入的元素） .

heapreplace()

相当于先弹出，然后压入，附加限制是保证堆大小在此过程中不会改变。这意味着您会在空堆上遇到错误，以及其他有趣的角落行为。

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

（实际上不是Python api），在幕后，这个功能与

heapq.pop()

非常相似

您会注意到这些函数在解决诸如“合并 K 个排序数组”之类的问题时非常方便。如果你只使用 pop +

push

（就像在java中一样），它会慢两倍:(

Answer 4

heapq.heappushpop

相当于

先推后弹出

同时

heapq.heapreplace

相当于

先弹出然后推

作为演示：

>>> 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]

Answer 5

此评论

中的解释除了从以结果为导向的角度来看的其他答案之外可能有用：

heappushpop
• 当您想要

  维护历史记录中的顶部-

  k时（因此新项目可能会离开）。它首先比较顶部项目和新项目。
heapreplace
• 当

  新项目必须位于堆上时

  （因此顶部项目离开）。这是通过直接用新项目替换顶部项目并重新堆化来完成的。