Heap Implementation From Scratch

Description

PriorityQueue hides a small, elegant data structure. Knowing how it works explains its costs (why peek is O(1) and remove(Object) is O(n)), why iterating it isn't sorted, and how to build variants the library lacks, such as a heap with decrease-key.

This skill builds a binary heap by hand: the array layout and its index arithmetic, sift-up and sift-down, bottom-up heapify in O(n), and heapsort.

We'll go from simple to more technical:

1. The pattern: an array as a complete tree, insert with sift-up, extract with sift-down.
2. A second flavor: build a heap in O(n) from the bottom up, then heapsort in place.
3. Where binary heaps run (priority queues, schedulers, Dijkstra, simulations).
4. What breaks it: the wrong child, holes, treating the array as sorted, empty values.

The approach

int[] heap = new int[capacity];
int size = 0;

void insert(int val) {
    int i = size++;
    heap[i] = val;                                        // append at the end
    while (i > 0 && heap[(i - 1) / 2] > heap[i]) {        // sift up while smaller than the parent
        swap(i, (i - 1) / 2);
        i = (i - 1) / 2;
    }
}

int extractMin() {
    if (size == 0) return -1;
    int min = heap[0];
    heap[0] = heap[--size];                               // move the last element to the root
    int i = 0;
    while (true) {                                        // sift down toward the SMALLER child
        int left = 2 * i + 1, right = left + 1, smallest = i;
        if (left < size && heap[left] < heap[smallest]) smallest = left;
        if (right < size && heap[right] < heap[smallest]) smallest = right;
        if (smallest == i) break;
        swap(i, smallest);
        i = smallest;
    }
    return min;
}

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, val: int) -> None:
        heap = self.heap
        heap.append(val)                                     # append at the end
        i = len(heap) - 1
        while i > 0 and heap[(i - 1) // 2] > heap[i]:        # sift up while smaller than the parent
            heap[i], heap[(i - 1) // 2] = heap[(i - 1) // 2], heap[i]
            i = (i - 1) // 2

    def extract_min(self) -> int:
        heap = self.heap
        if not heap:
            return -1
        smallest = heap[0]
        last = heap.pop()
        if heap:
            heap[0] = last                                   # move the last element to the root
            i = 0
            while True:                                      # sift down toward the SMALLER child
                left, right, best = 2 * i + 1, 2 * i + 2, i
                if left < len(heap) and heap[left] < heap[best]:
                    best = left
                if right < len(heap) and heap[right] < heap[best]:
                    best = right
                if best == i:
                    break
                heap[i], heap[best] = heap[best], heap[i]
                i = best
        return smallest

The array is the tree: a complete binary tree stored level by level, so node i's children are 2i + 1 and 2i + 2 and its parent is (i - 1) / 2 - node 5's parent is 2, its children 11 and 12. Completeness (no gaps) is what makes the index arithmetic work, and it's why extract moves the last element to the root. Sifting down must swap with the smaller child: swapping with the left child only puts a larger value above a smaller one.

A second flavor: build in O(n), sort in place

Turning an existing array into a heap by inserting one at a time costs O(n log n). Sifting down from the last parent back to the root costs O(n):

for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);      // heapify bottom-up

for i in range(n // 2 - 1, -1, -1):                          # heapify bottom-up
    sift_down(a, i, n)

# heapq.heapify(a) does exactly this, in place, in O(n)

Half the nodes are leaves (no work), a quarter sift at most one level, an eighth two levels, and so on - the total is under 2n swaps. For 2^20 values it made about 1.05 million swaps, against 21 million for n log n.

Heapsort builds a max-heap this way, then repeatedly swaps the root (the maximum) to the end and sifts down the shrunken heap: O(n log n) worst case, O(1) extra space, not stable.

Where you'll see it

java.util.PriorityQueue is exactly this array heap (with a comparator); OS schedulers and timer wheels, Dijkstra's and Prim's algorithms, and event-driven simulations all run on binary heaps. Knowing that iteration isn't sorted - new PriorityQueue<>(List.of(5, 1, 4, 2, 3)) iterates as [1, 2, 4, 5, 3] - avoids a classic bug when printing or streaming a queue's contents. Python's heapq is this same array heap on a plain list: h = [5, 1, 4, 2, 3]; heapq.heapify(h) leaves [1, 2, 4, 5, 3] - a valid heap, not a sorted list.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. In a 0-based array heap, what are the parent and children of index 5?

2. Why does extract move the last element to the root instead of shifting everything up?

3. Why is bottom-up heapify O(n) rather than O(n log n)?

Key takeaways

• Heap = complete binary tree in an array: children 2i + 1, 2i + 2; parent (i - 1) / 2.
• Insert: append and sift up. Extract: move the last element to the root and sift down to the smaller child.
• Build bottom-up in O(n); heapsort is O(n log n), in place, not stable.
• Iterating a PriorityQueue isn't sorted; remove(Object) is O(n); there's no decrease-key.