Heaps

A heap is a structure that always lets you grab the smallest (or largest) item quickly, which is exactly what a priority queue needs. It’s a binary tree with one rule: every parent is smaller than its children, so the minimum sits at the top. The tree is kept perfectly filled level by level, which means it can be stored as a plain array with no pointers. Adding or removing an item swaps it up or down one path of the tree, taking time proportional to the tree’s height, which is about log n. Heaps power task schedulers, Dijkstra’s shortest-path algorithm, “top k” queries and heapsort.