Python heapq heappushpop and heapreplace Guide

Python’s heapq module provides two specialized functions for combining insertion and extraction operations on priority queues: heappushpop() and heapreplace(). While both functions execute both a push and a pop within a single step to optimize performance, they differ in the sequence in which these actions occur. Understanding the order of execution between these two functions is essential for managing heap invariants, building fixed-size priority queues, and avoiding subtle algorithmic bugs.

heapq.heappushpop(heap, item): Push Then Pop

The heappushpop() function implements a combined push-then-pop operation:

  1. It logically adds the new item to the heap.
  2. It then removes and returns the smallest element from the heap (the root of the min-heap).

Because it pushes before popping, the value returned might be the exact item that was just passed into the function if that item is smaller than or equal to the existing root.

import heapq

heap = [5, 7, 9]
heapq.heapify(heap)

# Push 3, then pop the smallest
result = heapq.heappushpop(heap, 3)

print(result)  # 3 (the pushed item was smaller than 5)
print(heap)    # [5, 7, 9] (heap content remains unchanged)

If the heap is empty, heappushpop() simply returns the item passed into it without raising an error, leaving the heap empty.

heapq.heapreplace(heap, item): Pop Then Push

The heapreplace() function implements a combined pop-then-push operation:

  1. It removes and returns the current smallest element from the heap.
  2. It then inserts the new item into the heap and restores the heap invariant.

Because the pop occurs first, the returned item is guaranteed to be from the original heap, never the newly inserted item (even if the new item is smaller than the current root).

import heapq

heap = [5, 7, 9]
heapq.heapify(heap)

# Pop the smallest, then push 3
result = heapq.heapreplace(heap, 3)

print(result)  # 5 (the original root)
print(heap)    # [3, 7, 9] (3 replaces 5 as the new root)

If the heap is empty, heapreplace() raises an IndexError because there is no root element to pop before inserting the new element.

Key Differences

Feature heapq.heappushpop() heapq.heapreplace()
Operation Order Push first, then pop Pop first, then push
Empty Heap Behavior Returns the inserted item Raises IndexError
Can Return Input Item? Yes, if item <= heap[0] No, always returns prior root
Common Use Case Streaming top-\(k\) largest items Fixed-size priority queues

Why Use These Combined Operations?

Calling heappushpop() or heapreplace() is significantly faster than executing heappush() followed by heappop() (or vice versa).

Separate operations require two \(O(\log n)\) passes to rebalance the binary tree: one sift-up for the push and one sift-down for the pop. The combined functions reuse the existing root position in memory and perform only a single sift-down pass, running in \(O(\log n)\) time with roughly half the comparison and pointer overhead.