Heaps / Priority Queues

A tree-shaped structure that keeps the min (or max) element accessible in O(1), with O(log n) insert and remove.

Study first: Trees

What it is

A binary heap is a complete binary tree stored in an array, satisfying the heap property: every parent is ≤ (min-heap) or ≥ (max-heap) its children. That property guarantees the smallest (or largest) element is always at the root.

Core operations

Peek — O(1), it's the root.
Push / pop — O(log n): insert at the end and "bubble up," or replace the root with the last element and "bubble down," restoring the heap property.
Heapify — building a heap from n elements in O(n) (not O(n log n)) by heapifying from the bottom up.

Why not just sort?

Sorting the whole collection is O(n log n) up front. A heap gives you the running min/max in O(log n) per update as elements are added or removed over time — the right tool when you need "the current smallest" repeatedly, not a one-time full order.

Where it shows up

Top-k problems, merging k sorted lists, Dijkstra's shortest path, and task schedulers all reduce to "repeatedly grab the current best element."