Heap: keep the next extreme ready
Picture
Tasks cost 5,1,4. We need the cheapest task now, then the next cheapest after adding new tasks.
Predict
Does iterating the internal heap array return sorted order?
Walk through the small example
No. Only the next extreme matters; complete sorted order is unnecessary.
Mental model and complete Python solution
A heap is a waiting room with one promise: the best priority is at the front. The rest is arranged only enough to restore that promise after each change.
What the function promises: Return values in sorted order by repeatedly popping a min-heap. This demonstration copies the input.
from heapq import heapify, heappop
def heap_order(values):
heap = list(values)
heapify(heap)
return [heappop(heap) for _ in range(len(heap))]
assert heap_order([5,1,4,1]) == [1,1,4,5]
assert heap_order([]) == []Work and storage: Heap construction is O(n); all n pops cost O(n log n). Peek is O(1), push/pop are O(log n).
When to recognize it: Only the next extreme matters; complete sorted order is unnecessary.
Check before applying it: A heap does not support arbitrary search or stable tie order unless extra fields provide it.
Change one rule
Priority values tie and insertion order must break ties.
See what changes
Store tuples such as (priority, sequence_number, item) with a growing sequence number.
Connect
bst heap: The heap invariant orders parents against children, not every pair.
dijkstra: A heap chooses the cheapest waiting graph state.