Core Data Structures

Heaps & Priority Queues

A binary heap is a complete binary tree stored implicitly in an array, maintaining the invariant that every parent is smaller (min-heap) or larger (max-heap) than its children. It is the standard implementation of the priority queue ADT: O(log n) insert, O(log n) extract-min/max, O(1) peek.

Complete binary tree stored in an array: node at index i has children at 2i+1 and 2i+2, parent at (i-1)/2 — no pointers needed
Min-heap property: every parent ≤ both children (recursively) — the minimum is always at the root, not necessarily anywhere else specific
insert (sift-up) and extractMin (sift-down) are both O(log n); peekMin is O(1)
Building a heap from n unordered elements is O(n), not O(n log n) — bottom-up heapify does less work than n sequential inserts
Java's PriorityQueue is a min-heap by default; pass a Comparator for max-heap or custom ordering
A heap is only "sorted" at the root — it is not a fully sorted structure, which is exactly what makes building it fast

Binary heap operation costs
Operation	Cost	Mechanism
`peek` (min/max)	O(1)	Always at index 0
`insert`	O(log n)	Append at end, sift up
`extractMin`/`extractMax`	O(log n)	Swap root with last, remove last, sift down
`heapify` (build from n elements)	O(n)	Bottom-up sift-down from last internal node

Sift-up (insert) and sift-down (extract) on an array-backed min-heap

int[] heap; int size;

void siftUp(int i) {
    while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
        swap(i, (i - 1) / 2);
        i = (i - 1) / 2;
    }
}

int extractMin() {
    int min = heap[0];
    heap[0] = heap[--size];       // move last element to root
    siftDown(0);
    return min;
}

void siftDown(int i) {
    while (true) {
        int l = 2 * i + 1, r = 2 * i + 2, smallest = i;
        if (l < size && heap[l] < heap[smallest]) smallest = l;
        if (r < size && heap[r] < heap[smallest]) smallest = r;
        if (smallest == i) break;
        swap(i, smallest);
        i = smallest;
    }
}

Heapsort (Heapsort) is exactly "build a heap in O(n), then extract the minimum n times" — O(n) + n·O(log n) = O(n log n) total, in place, with no extra memory. This is also the mechanism behind the top-K interview pattern (Heap Top K Pattern): maintain a heap of size k instead of sorting everything, turning an O(n log n) full sort into O(n log k).

A heap is not a sorted array — do not iterate it expecting order

Only the root is guaranteed to be the min (or max); the rest of the array satisfies the heap property but is not otherwise ordered. Iterating a PriorityQueue directly (via its iterator, not repeated poll()) gives elements in heap array order, not priority order — a frequent source of confusion.

Java

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.addAll(List.of(5, 1, 4, 2));
// pq.iterator() does NOT guarantee ascending order — only pq.poll() repeatedly does