CODEWITHSUNDEEP
python-3.xheap
kolman
kolman

Reputation: 402

How is heapq.heappushpop more efficient than heappop and heappush in python

In the docs for heapq, its written that

heapq.heappushpop(heap, item)

Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().

Why is it more efficient?
Also is it considerably more efficient ?

Upvotes: 5

Views: 2196

Answers (2)

RoadBiker
RoadBiker

Reputation: 21

heappushpop pushes an element and then pops the smallest elem. If the elem you're pushing is smaller than the heap's minimum, then there's no need to do any operations., because we know that the element we're trying to push (which is smaller than the heap min), will be popped if we do it in two operations.

This is efficient, isn't it?

Upvotes: 2

patpat
patpat

Reputation: 704

  • heappop is pop out the first element, then move the last element to fill the in the first place, then do a sinking operation, which moving the the element down through consecutive exchange. thus restore the head
    it is O(logn)
    then you headpush, place the element in the last place, and bubble-up like heappop but reverse
    another O(logn)

  • while heappushpop, pop out the first element, instead of moving the last element to the top, it place the new element in the top, then do a sinking motion. which is almost the same operation with heappop.
    just one O(logn)

as above even though they are both O(logn), it is easier to see heappushpop is faster than heappop then heappush.

Upvotes: 7

Related Questions