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

Question

I couldn't figure out the difference (other than ordinality of push/pop actions) between functions heapq.heappushpop() and heapq.heapreplace() when i tested out 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]

Tedi

Answer 1

heapreplace(a, x) returns the smallest value originally in a regardless of the value of x, while, as the name suggests, heappushpop(a, x) pushes x onto a before popping the smallest value. Using your data, here's 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

Hamforrd

Answer 2

in many common cases the ultimate result seems the same, but the process and behavior is different, and can be visible in corner cases:

heappushpop() is equivalent to pushing first, then popping, meaning, amongst other things, that your heap size might change in the process (and that, for example, if your heap is empty you'll get back the element you pushed).

heapreplace() is equivalent to popping first, then pushing, with the additional restriction of guaranteeing that your heap size won't change in the process. this means you'll get an error on an empty heap, amongst other interesting corner behaviour.

Voccola

Can you add what are the other interesting corner behavior? – Passable

Answer 3

Very important to know that the reason heapq have these methods is to increase efficiency
In terms of functionality, you can think like this

# 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 

but why having two additional functions when you can do everything with push,pop? heapq.heappushpop() and heapq.heapreplace() only use log(K) time!

# 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

the time consuming operation is heapq.bubbledown(not actually a python api), under the hood, this function is very similar to heapq.pop()

You will notice these functions are very handy when it comes to solve problems like Merge K sorted arrays. If you just use pop + push (like in java), it will be two times slower :(

Theosophy

Can you explain more why heapq.bubbledown is only log(K) time? – Babel

@Babel because bubble down needs to take at most h steps, where h is the height of the heap. With every step it goes down one level in that tree. And h is log(K). – Holding

Although the chosen answer answers the question, this is much more infromative and useful. Thanks! – Shep

Answer 4

heapq.heappushpop is equivalent to first push then pop

while

heapq.heapreplace is equivalent to first pop then push

as a demo:

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

Melon

Just to add to @Syscall comment this link is helpful for new user's: stackoverflow.com/help/how-to-answer – Oxendine

Answer 5

My explanation in this comment might be useful in addition to other answers from a result-oriented perspective:

• heappushpop when you'd like to maintain the top-k over the history (so the new item may leave). It first compares the top item and the new item.
• heapreplace when the new item must be on the heap (so the top item leaves). This is done by directly replacing the top item with the new item and re-heapifying.

Agram