heapq Module & Min-Heap Priority Queue Algorithms

1Concept

The `heapq` module implements binary min-heaps on top of standard Python lists (where `heap[0]` is always the minimum element). In-place heap operations (`heappush`, `heappop`) run in O(log N) time.

2Architecture Diagram

Binary Min-Heap Property: Parent <= Children
            [ 10 ]
           /      \
       [ 30 ]    [ 20 ]

3Code Example

import heapq

tasks = []
# Priority Queue entries: (priority, task_name)
heapq.heappush(tasks, (3, "Routine Backup"))
heapq.heappush(tasks, (1, "Security Patch P0"))
heapq.heappush(tasks, (2, "Database Reindex"))

print(f"Top Priority Task: {heapq.heappop(tasks)}")
print(f"Next Task:         {heapq.heappop(tasks)}")

# Top-N largest items from list
numbers = [85, 12, 59, 99, 44, 102, 33]
print(f"Top 3 Numbers:     {heapq.nlargest(3, numbers)}")

4Expected Output

Top Priority Task: (1, 'Security Patch P0')
Next Task:         (2, 'Database Reindex')
Top 3 Numbers:     [102, 99, 85]

5Key Takeaways

• ✓`heapq` implements a MIN-heap; negate numbers (`-val`) to simulate a MAX-heap.
• ✓`heapq.heapify(list)` converts a list into a valid min-heap in O(N) linear time.
• ✓`nlargest(k)` and `nsmallest(k)` avoid full O(N log N) sorting when k << N.