Min-Heap — Next Patient, Next Task, Next Event

A min-heap is a binary tree where each parent is ≤ its children. The minimum is always at the root, making “give me the next smallest” O(log n)—the backbone of heap sort and priority queues.

Why this shows up in the real world

Hospital triage systems pop the most urgent patient next—that is a min-heap on priority keys. Packet schedulers pick the smallest deadline first. Game matchmaking may always serve the player who has waited longest by using a heap keyed on wait time. Understanding min-heap semantics explains why heapq in Python is min-ordered.

Core idea (explained for students)

heapq.heappush inserts by bubbling up; heappop removes the root and sifts down. Internally Python uses a 0-based array representation. For max-heap patterns, store negated keys. Duplicate priorities need a tie-breaker counter in the tuple to avoid comparing incomparable objects.

Try this in Python

import heapq

h = []
for x in [4, 1, 3, 2]:
    heapq.heappush(h, x)
while h:
    print(heapq.heappop(h), end=" ")
print()

Common mistakes

• Comparing tuples with unequal types—TypeError.
• Thinking heapq is a max-heap—it's not.
• Mutating objects after push breaks heap property.

Key takeaways

• Root is global min in min-heap.
• Operations O(log n) push/pop.
• Tuple keys encode multi-field priorities.