pythonheap

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


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]

Solution

  • 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