Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

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] 
like image 382
Ayush Avatar asked Nov 13 '15 20:11

Ayush


People also ask

What is Heapreplace in Python?

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().

What is Heappushpop Python?

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.

Is Heapq Minheap or Maxheap?

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.

Why do we use Heapq in Python?

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.


1 Answers

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 
like image 164
Tim Peters Avatar answered Sep 28 '22 18:09

Tim Peters