The example problem
Keep a collection where you can always add a value and take out the smallest value quickly (a min-heap / priority queue).
Input: patients arrive with severities 5, 3, 8, 1, 6 Output: they are treated in order 1, 3, 5, 6, 8
Picture it
Picture hospital triage: the most urgent patient (smallest number) must always be seen first. The heap is a tree where every parent is more urgent than its children, so the most urgent is at the top. A new patient joins at the bottom and bubbles up past less urgent parents. When the top patient leaves, the last one moves to the top and sinks down.
The key idea
A heap keeps only partial order (parent ≤ children), stored as a list. Push and pop are O(log n).
Python
def push(heap, x):
heap.append(x)
i = len(heap) - 1
while i > 0 and heap[(i - 1) // 2] > heap[i]:
p = (i - 1) // 2
heap[i], heap[p] = heap[p], heap[i]
i = p
def pop(heap):
top = heap[0]
heap[0] = heap.pop() # last patient to the top
sift_down(heap, 0) # let them sink
return topPractise heap
NeetCode 150 problems that use it
Heap / Priority Queue ·
- LeetCode 703 · EasyKth Largest Element in a StreamA podium with k places as scores keep arriving
- LeetCode 1046 · EasyLast Stone WeightSmashing the two heaviest rocks together
- LeetCode 973 · MediumK Closest Points to OriginThe k cafés nearest your home
- LeetCode 215 · MediumKth Largest Element in an ArrayA podium that only keeps the top k
- LeetCode 621 · MediumTask SchedulerA chef whose stations need time to cool down
- LeetCode 355 · MediumDesign TwitterA news feed merged from the people you follow
- LeetCode 295 · HardFind Median from Data StreamTwo waiting rooms with the median at the door