Heap Fundamentals

A binary heap is a complete binary tree (every level filled left-to-right, except possibly the last) where every node's value is less than or equal to its children's (a min-heap) or greater than or equal (a max-heap). The root holds the smallest (or largest) element.

The array layout

Because heaps are complete, they fit perfectly into an array. The root is at index 0. For node $i$, its children are at $2i + 1$ and $2i + 2$; its parent is at $\lfloor (i - 1)/2 \rfloor$. No pointers, no allocator overhead, cache-friendly access.

The two key operations

• Sift up (used after insert): the new element starts at the end of the array. Compare with its parent; swap if it violates the heap property; repeat until it's in place or it reaches the root. $O(\log n)$.
• Sift down (used after extract): replace the root with the last element, then swap with the smaller child repeatedly until the heap property holds. $O(\log n)$.

Heapify

Build a heap from an unsorted array of size $n$ in $O(n)$ — not $O(n \log n)$ as you'd expect. Start from the last non-leaf and sift each element down. The clever analysis: most nodes are near the leaves and sift down by only a small amount; the total work sums to $O(n)$.

Priority queue

The abstract data type that heaps implement. Insert, find-min (or max), and extract-min are the main operations. Python's heapq is a min-heap of a list; Java's PriorityQueue is a min-heap by default; C++'s std::priority_queue is a max-heap.

What heaps aren't

They aren't sorted — only the root is at the extreme. Iterating a heap in order takes $O(n \log n)$ via repeated extracts (this is heap sort). If you need sorted order at all times, use a balanced BST, not a heap.