Heap / Priority Queue

How it works

A binary heap is a complete tree where every parent dominates its children (min-heap: smaller; max-heap: larger). Stored compactly in an array, it gives O(1) peek at the extreme and O(log n) insert/extract via sift-up and sift-down.

Mental models

• Array indexing: children of i are 2i+1 and 2i+2 — no pointers needed.
• Insert at the end, then bubble up until the heap property holds.
• Extract swaps root with last, shrinks, then sinks the new root down.