Why it matters
Priority queues are one of the most-used data structures. Wrong choice (linked list vs sorted array vs heap) has 100x impact on performance. Heaps are usually the answer.
The architecture
Array representation: parent(i) = (i-1)/2, left(i) = 2i+1, right(i) = 2i+2. No pointers needed.
Insert: append at end, bubble up (swap with parent while out of order). O(log n).
Extract-min: return root, move last to root, bubble down (swap with smaller child). O(log n).
How it works end to end
Heapify: convert unordered array to heap in O(n). Bubble down from last non-leaf backwards. This is faster than n inserts.
Heap sort: heapify array, then repeatedly extract-min into a result. O(n log n), in-place, not stable.
d-ary heaps: nodes have d children instead of 2. Shallower tree, more comparisons per level. Sometimes faster in practice.
Fibonacci heap: better amortized decrease-key. Theoretically improves Dijkstra to O(E + V log V).