Python heapq.heappushpop() Method

heapq.heappushpop() method inserts a new element into a heap and then removes and returns the smallest element. It performs both operations in a single step while maintaining the heap property, making it more efficient than calling heappush() and heappop() separately.

Example: In the code below, we add a new element to the heap and remove the smallest element in a single operation.

import heapq

h = [2, 4, 6, 8]
heapq.heapify(h)

x = heapq.heappushpop(h, 5)
print(x)
print(h)

2
[4, 5, 6, 8]

Explanation: heapq.heappushpop(h, 5) inserts 5 into the heap and removes the smallest element (2). The removed value is returned and the heap is updated automatically.

Syntax

heapq.heappushpop(heap, item)

Parameters:

• heap: A valid heap (list).
• item: The element to insert into the heap.

Return Value: Returns the smallest element after performing the push-pop operation.

Working of heapq.heappushpop()

heapq.heappushpop() first inserts the new element into the heap and then removes the smallest element. The heap is automatically rearranged after the operation to preserve the min-heap property.

Example 1: In the code below, we insert a new number into the heap and remove the smallest element in a single operation.

import heapq

h = [1, 3, 5, 7]
heapq.heapify(h)

x = heapq.heappushpop(h, 4)
print("Removed:", x)
print("Heap:", h)

Removed: 1
Heap: [3, 4, 5, 7]

Explanation: heapq.heappushpop(h, 4) adds 4 and removes the smallest element 1. The heap is then rearranged to maintain the heap property.

Example 2: In the code below, tasks are stored as (priority, task) tuples. Lower priority values are processed first.

import heapq

pq = [(2, "Task A"), (3, "Task B")]
heapq.heapify(pq)

x = heapq.heappushpop(pq, (1, "Task C"))
print("Removed:", x)
print("Queue:", pq)

Removed: (1, 'Task C')
Queue: [(2, 'Task A'), (3, 'Task B')]

Explanation: Since (1, "Task C") is smaller than all existing elements, heappushpop() immediately returns it and leaves the heap unchanged.

Example 3: In the code below, a fixed-size heap is used to keep track of the highest scores.

import heapq

h = [50, 60, 70]
heapq.heapify(h)

x = heapq.heappushpop(h, 65)
print("Removed:", x)
print("Scores:", h)

Removed: 50
Scores: [60, 65, 70]

Explanation: heapq.heappushpop(h, 65) removes the smallest score 50 and inserts 65, helping maintain the top scores in the heap.

When to Use heapq.heappushpop()

Use heapq.heappushpop() when:

• You need to insert a new element and remove the smallest element in one operation.
• You are maintaining a fixed-size heap.
• Performance is important and frequent heap updates are required.
• You want a more efficient alternative to calling heappush() and heappop() separately.