Heap
A complete binary tree where every parent beats its children (min or max). The winner sits at the root for O(1) reading; insert and extract are O(log n). Stored flat in an array.
A min-heap keeps one promise at every node: parent ≤ children. Nothing about left vs right — it is far weaker than a BST's ordering, and that weakness is what makes it cheap to maintain. The minimum is always at index 0.
The tree lives in a plain array: children of index i sit at 2i+1 and 2i+2, parent at (i−1)/2. Insert appends at the end and bubbles up while smaller than its parent — at most log n swaps. Extract-min swaps the last element into the root and sifts it down. Building a heap from n items bottom-up is only O(n).
Heaps are the standard priority queue: Dijkstra and A* pull their next frontier node from one, heapsort extracts repeatedly, schedulers pick the next deadline, and "top-k of a stream" keeps a k-sized heap instead of sorting everything.
Operations
| Operation | Complexity |
|---|---|
| peek min/max | O(1) |
| insert | O(log n) |
| extract | O(log n) |
| build from array | O(n) |
Where it's used
Priority queues everywhere: pathfinding frontiers, schedulers, event simulation, top-k queries, heapsort.