Heaps

A heap is a tree where every parent is ≥ its children (max-heap) or ≤ its children (min-heap), usually stored as an array for efficiency. It gives you O(1) access to the extremum and O(log n) insert and extract — exactly the operations a priority queue needs. Any time you want "process the highest-priority thing next", a heap is the right tool: task schedulers, Dijkstra's shortest path (pop the closest unvisited node), A* pathfinding, finding top-k in a stream (keep a size-k min-heap, swap if new element is larger). Heapsort uses the same structure: heapify, then repeatedly extract-max into the end of the array — O(n log n), in-place, but usually slower in practice than quicksort because of cache behaviour.