Data Structure
Heap
A complete binary tree that keeps the smallest (or largest) element at the root, giving O(1) peek and O(log n) insert/remove — the engine behind priority queues.
Always know the top priority.
A heap is a special tree that always keeps the most important item (smallest for a min-heap, largest for a max-heap) at the top. You can peek at that top item instantly, and adding or removing keeps the heap ordered.
- peek — see the min/max in O(1).
- push / pop — add or remove the top in O(log n).
- Perfect when you repeatedly need "the next smallest/largest."
Array-backed, sift up/down.
A heap is stored compactly in an array (no pointers): for index i, its
children are 2i+1 and 2i+2, and its parent is (i-1)/2.
- Insert — append at the end, then sift up while smaller than the parent.
- Extract-min — swap root with last, remove it, then sift down.
- Heapify — build a heap from an array bottom-up in O(n).
Applications and variants.
- Heapsort — build a heap then repeatedly extract; O(n log n), in-place, not stable.
- Dijkstra / Prim / A* — priority queues pick the next best node efficiently.
- Top-k / streaming medians — a bounded heap (or two heaps) tracks top-k or the running median.
- Advanced heaps — binary vs binomial vs Fibonacci heaps trade decrease-key cost;
d-ary heaps tune fanout for cache/write patterns.