python, heapq: difference between heappushpop() and heapreplace()
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
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.
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) == kheapq.heappushpop(list, elem): # 2*log(K) runtime heapq.push(list, elem) # log(K) runtime return heapq.pop(list) # log(k) runtimeheapq.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) == kheapq.heappushpop(list, elem): # log(K) runtime if elem < list[0]: return elem return heapq.heapreplace(list, elem) # log(K) runtimeheapq.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 :(