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]
The heapreplace method pops and returns the smallest element from the heap then pushes the given element into the heap. This method is equivalent to heappop() followed by heappush().
The function heappushpop() of the heapq module in Python removes and returns the smallest element (i.e., the root node) from a min heap after an item is pushed into the heap. The heap property is maintained all the time.
The heapq module of python implements the heap queue algorithm. It uses the min heap where the key of the parent is less than or equal to those of its children.
Heap queue is a special tree structure in which each parent node is less than or equal to its child node. In python it is implemented using the heapq module. It is very useful is implementing priority queues where the queue item with higher weight is given more priority in processing.
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With