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

Question

I could not understand the difference (other than the usual push / pop actions) between the heapq.heappushpop () and heapq.heapreplace () functions when I tested the following code.

>>> 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)returns the smallest value initially in aregardless of the value x, whereas, as the name implies, heappushpop(a, x)clicks xon abefore displaying the smallest value. Using your data, here is a sequence that shows the difference:

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

time-consuming operation heapq.bubbledown(not really python api), under the hood this function is very similar toheapq.pop()

You will notice that these functions are very convenient when you have to solve problems such as Merge sorted arrays . If you just use pop+ push(e.g. in java), this will be twice as slow: (