Python heapq.heappush() Method

The heapq.heappush() function in Python is used to push an element onto a heap while maintaining the heap property. This function is useful when dealing with priority queues or implementing efficient sorting algorithms.

Example:

import heapq # Create an empty list that will represent the heap h = [] # Use heappush to add elements to the heap heapq.heappush(h, 10) heapq.heappush(h, 5) heapq.heappush(h, 20) heapq.heappush(h, 15) # Print the heap after adding elements print(h) 

[5, 10, 20, 15] 

Explanation:

• The heappush() function ensures that the heap property is maintained, meaning the smallest element is always at the root (index 0).
• After pushing the values 10, 5, 20, and 15, the heap is automatically rearranged to maintain the heap property.

Syntax of heappush() method

heapq.heappush(heap, item)

Parameters

• heap: The list representing the heap (must be a valid heap structure).
• item: The element to be pushed onto the heap.

Return Value

This function does not return anything. It modifies the heap in-place by inserting the new element while maintaining the heap property.

Examples of heappush() method

1. Using heappush() to Insert Elements in a Min-Heap

import heapq # Create an empty heap h = [] # Push elements onto the heap heapq.heappush(h, 5) heapq.heappush(h, 1) heapq.heappush(h, 8) heapq.heappush(h, 3) print("Min-Heap:", h) 

Min-Heap: [1, 3, 8, 5] 

Explanation:

• The heappush() function is used to insert the values 5, 1, 8, and 3 into the heap.
• The heap automatically rearranges itself to maintain the min-heap property, where the smallest element is always at the root (index 0).

2. Using heappush() in a Max-Heap

Since heapq only supports min-heaps, we can simulate a max-heap by pushing negative values.

import heapq h = [] # Push elements as negative values to simulate max-heap heapq.heappush(h, -5) heapq.heappush(h, -1) heapq.heappush(h, -8) heapq.heappush(h, -3) # Convert back to positive for correct order max_heap = [-x for x in h] print("Max-Heap:", max_heap) 

Max-Heap: [8, 3, 5, 1] 

Explanation:

• Elements are pushed onto the heap as negative values (-5, -1, -8, -3) to simulate the behavior of a max-heap.
• The heappush() function inserts the negative values, maintaining the min-heap property on the negative values, which results in a simulated max-heap.
• After inserting all elements, the heap is converted back to positive values using list comprehension ([-x for x in h]) to display the correct max-heap order.

3. Using heappush() in a Priority Queue

heapq.heappush() is commonly used in priority queues, where elements are inserted based on their priority.

import heapq # List of tuples (priority, task) pq= [] # Push elements (priority, task) heapq.heappush(pq, (2, "Task A")) heapq.heappush(pq, (1, "Task B")) heapq.heappush(pq, (3, "Task C")) print("Priority Queue:", pq) 

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

Explanation:

• Elements are pushed onto the heap as tuples, where the first value is the priority (lower values indicate higher priority) and the second value is the task.
• The heappush() function ensures that the queue is sorted according to the priority, with the element having the lowest priority value at the root.