Heaps

A heap keeps the smallest (or largest) element instantly available, without keeping everything sorted. It is the structure behind PriorityQueue, and it is stored in a flat array with no node objects at all.

Two ideas

The heap property. Every node is ≤ its children (a min-heap). So the minimum is always at the root. Note what this does not say: nothing relates siblings, and nothing relates a node to its cousins. It is a much weaker condition than being sorted, which is exactly why it is cheap to maintain.

The array layout. A heap is a complete binary tree — every level full except possibly the last, which fills left to right. That regularity means the tree structure can be implied by arithmetic instead of stored:

parent(i) = (i - 1) / 2      left(i) = 2i + 1      right(i) = 2i + 2

        1              index:  0  1  2  3  4  5
       / \             array: [1, 3, 2, 8, 5, 9]
      3   2
     / \   \
    8   5   9

No Node objects, no references, no allocation per element — and the whole thing is contiguous, which is exactly what caches reward. A heap is the cheapest tree there is because it is not really a tree in memory.

Insert: sift up

    private void siftUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (items[index] >= items[parent]) {
                break;
            }
            swap(index, parent);
            index = parent;
        }
    }

Put the new element at the end — the only place that keeps the tree complete — then swap it upwards while it is smaller than its parent. At most the height of the tree, so O(log n).

Remove the minimum: sift down

    public int poll() {
        if (size == 0) {
            throw new NoSuchElementException("heap is empty");
        }
        int min = items[0];
        items[0] = items[--size];
        siftDown(0);
        return min;
    }

The move that makes this work: promote the last element to the root, then sift it down. Promoting a child instead would leave a hole in the middle of the array and break the complete-tree layout that every index calculation depends on.

    private void siftDown(int index) {
        while (true) {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int smallest = index;

            if (left < size && items[left] < items[smallest]) {
                smallest = left;
            }
            if (right < size && items[right] < items[smallest]) {
                smallest = right;
            }
            if (smallest == index) {
                return;
            }
            swap(index, smallest);
            index = smallest;
        }
    }

Swap with the smaller of the two children. Swapping with either one that happens to be smaller than the parent is the common bug: the element moves down, but the child you promoted may be larger than its new sibling, and the heap property breaks silently.

Costs

That last row is the trade. A heap gives you the minimum for free and knows nothing else — finding some particular element means scanning the array, because the heap property gives you no way to choose a direction.

⚠️ A heap is not sorted

Only the root is guaranteed. [1, 3, 2, 8, 5, 9] above is a valid heap and is obviously not in order.

The practical consequence catches people constantly: iterating a PriorityQueue does not give you sorted order, it gives you the array. To get sorted output you must poll() repeatedly — which is precisely heap sort, at O(n log n), and is what this assertion does:

        StringBuilder drained = new StringBuilder();
        while (!heap.isEmpty()) {
            drained.append(heap.poll()).append(' ');
        }
        Check.eq(drained.toString().trim(), "1 2 3 5 8 9", "polling repeatedly yields sorted order");

Heapify is O(n), not O(n log n)

This is the genuinely surprising result.

        heap.size = values.length;
        for (int i = values.length / 2 - 1; i >= 0; i--) {
            heap.siftDown(i);
        }

Adding n elements one at a time is n × O(log n) = O(n log n). But sifting down from the last parent backwards is O(n).

The reason is where the nodes are. Half the nodes are leaves and sift down zero levels. A quarter are one level up and move at most one. An eighth move at most two. Summing height × count over the tree gives n × Σ(k/2ᵏ), and that series converges to 2 — so the total is O(n), not O(n log n).

The intuition that misleads people is thinking about the root, which really can move log n levels. But there is only one root, and there are n/2 leaves that move nothing at all.

What heaps are for

Priority queues — the next post.

The top k of n. Keep a heap of size k and you get O(n log k) time and O(k) space, where sorting everything is O(n log n) and O(n). For "top 10 of a billion" that is the difference between fitting in memory and not.

        Check.eq(java.util.Arrays.toString(smallest(new int[] {9, 4, 7, 1, 8, 2}, 3)),
                "[1, 2, 4]", "three smallest");

Heap sort — heapify in O(n), then poll n times. O(n log n) guaranteed, in place, not stable. Rarely used alone because quick sort is faster in practice, but it is the fallback introsort switches to when quick sort degrades.

Dijkstra's algorithm — repeatedly take the nearest unvisited vertex, which is exactly a min-heap's job.

Duplicates are fine

Unlike the BST, which treated equal values as one, a heap is a multiset:

        Check.eq(dupes.size(), 3, "duplicates are kept");

What to remember

• Every node ≤ its children; only the root is guaranteed to be the minimum.
• Stored in a flat array — 2i+1, 2i+2, (i-1)/2.
• Insert sifts up, poll promotes the last element and sifts down.
• A heap is not sorted, and iterating one proves it.
• Heapify is O(n) because most nodes are leaves.
• Top-k with a size-k heap: O(n log k) time, O(k) space.