python，heapq:heappushpop（）和heapplace（）之间的区别

Question

我搞不清函数之间的区别（除了push/pop操作的有序性）heapq.heappushpop（）和heapq.heapplace公司（）当我测试以下代码时。在

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

要知道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()和{}只使用log（K）时间！

^{pr2}$

耗时的操作是heapq.bubbledown（实际上不是一个python api），实际上，这个函数非常类似于^{}

您会注意到这些函数在解决Merge K sorted arrays等问题时非常方便。如果您只使用pop+push（就像在java中一样），它将慢两倍：（

Answer 2

heapreplace(a, x)返回最初在a中的最小值，而不管x的值如何，而正如其名称所示，heappushpop(a, 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

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

heappushpop()相当于先推后弹出，这意味着堆大小可能会在进程中发生变化（例如，如果堆为空，则会取回推送的元素）。在

heapreplace()相当于先弹出，然后推送，附加的限制是保证堆大小在这个过程中不会改变。这意味着您将在空堆上得到一个错误，以及其他有趣的角落行为。在