☕ DSA Java Articles

Topics › Heaps › Learning

Heaps (Theory Video)

Easy TUF ID 1223 A2Z

Java source ↗ Edit this article ↗

What this covers

This row introduces the binary heap, the data structure behind every “give me the smallest (or largest) item, quickly, again and again” problem in this section. A heap answers “what is the minimum?” in O(1), and inserts or removes in O(log n), while sitting in a plain array with no pointers. The article builds one from scratch: the shape and ordering rules, the index arithmetic, the two repair operations (sift up and sift down), the two ways to build a heap and why one of them is linear, heap sort, and finally Java’s PriorityQueue, which is what you will use in practice. Every snippet comes from the Java file, whose main checks the outputs quoted here.

Two rules: shape and order

A min-heap is a binary tree that obeys two rules.

  1. Shape. The tree is complete: every level is full except possibly the last, and the last level is filled from the left with no gaps.
  2. Order. Every node is less than or equal to its children. By following parent links upward, this means every node is less than or equal to everything in its subtree, so the root holds the minimum.

A max-heap flips the order rule (every node is at least its children) and keeps the maximum at the root. Everything below works for both after flipping the comparisons.

Notice what the order rule does not say: nothing relates siblings or cousins. [1, 3, 2, 5, 9, 8] is a valid min-heap even though 3 comes before 2. A heap is only partially sorted, and that weaker promise is exactly what makes it cheap to maintain.

Storing the tree in an array

Because the tree is complete, we can write its nodes level by level, left to right, into an array with no holes. With 0-based indices, node i finds its relatives with arithmetic:

static int parent(int i) {
    return (i - 1) / 2;
}

static int left(int i) {
    return 2 * i + 1;
}

static int right(int i) {
    return 2 * i + 2;
}

For [1, 3, 2, 5, 9, 8] the root 1 (index 0) has children at 1 and 2 (3 and 2); node 3 (index 1) has children at 3 and 4 (5 and 9); node 2 (index 2) has a left child at 5 (8). The last internal (non-leaf) node is at n / 2 - 1; every index from n / 2 onward is a leaf. Some books use 1-based indices, where the formulas become i / 2, 2i and 2i + 1.

The order rule then becomes a one-line check: every non-root element must be at least its parent.

static boolean isMinHeap(int[] a, int n) {
    for (int i = 1; i < n; i++) {
        if (a[parent(i)] > a[i]) return false;
    }
    return true;
}

The height of a complete tree with n nodes is floor(log2 n). That number bounds every repair walk below, which is where the O(log n) costs come from.

Insert: append, then sift up

To insert, put the new value in the only place that keeps the shape legal, the first free slot at the end of the array. The shape is fine; the order may be broken between the new node and its parent. Fix it by swapping the node with its parent while it is smaller. Each swap moves the problem one level up, and it stops at the root at the latest.

static int siftUp(int[] heap, int i) {
    int swaps = 0;
    while (i > 0 && heap[parent(i)] > heap[i]) {
        swap(heap, i, parent(i));
        i = parent(i);
        swaps++;
    }
    return swaps;
}

Why is the rest of the tree still fine after a swap? The parent p that moves down was already at most all of its old children, and the value moving up is smaller than p, so both children of the new position are still at least the new value. Inserting 5, 3, 8, 1, 9, 2 one by one:

insert array after append sift-up swaps array after
5 [5] 0 [5]
3 [5, 3] 1 [3, 5]
8 [3, 5, 8] 0 [3, 5, 8]
1 [3, 5, 8, 1] 2 [1, 3, 8, 5]
9 [1, 3, 8, 5, 9] 0 [1, 3, 8, 5, 9]
2 [1, 3, 8, 5, 9, 2] 1 [1, 3, 2, 5, 9, 8]

Remove the minimum: move the last leaf up, then sift down

The minimum is heap[0]. To remove it while keeping the shape, move the last element into the root and shrink the size by one. Now the root may be too big. Swap it with its smaller child while some child is smaller than it. Choosing the smaller child matters: that child becomes the parent of the other one, and only the smaller of the two can legally sit above both.

static int siftDown(int[] heap, int n, int i) {
    int swaps = 0;
    while (true) {
        int smallest = i, l = left(i), r = right(i);
        if (l < n && heap[l] < heap[smallest]) smallest = l;
        if (r < n && heap[r] < heap[smallest]) smallest = r;
        if (smallest == i) return swaps;
        swap(heap, i, smallest);
        i = smallest;
        swaps++;
    }
}

Removing 1 from [1, 3, 2, 5, 9, 8] moves 8 to the root, giving [8, 3, 2, 5, 9]. Its children are 3 and 2; the smaller is 2, so they swap, giving [2, 3, 8, 5, 9], and index 2 has no children left, so we stop. Repeating this until the heap is empty produces the elements in increasing order:

static int[] drainInOrder(int[] heap) {
    int[] h = heap.clone();
    int n = h.length;
    int[] out = new int[n];
    for (int j = 0; j < out.length; j++) {
        out[j] = h[0];
        h[0] = h[--n];
        siftDown(h, n, 0);
    }
    return out;
}

Building a heap: n log n versus n

Given an unordered array, there are two ways to turn it into a heap in place. The first treats the prefix a[0..k-1] as a heap and inserts a[k] by sifting it up:

static long buildByInsertion(int[] a) {
    long swaps = 0;
    for (int k = 1; k < a.length; k++) swaps += siftUp(a, k);
    return swaps;
}

The second, bottom-up heapify, observes that every leaf is already a one-element heap. Walk the internal nodes from the last (n / 2 - 1) back to the root and sift each one down; when node i is processed, both of its subtrees are already heaps, so a single sift-down makes the subtree at i a heap.

static long buildBottomUp(int[] a) {
    long swaps = 0;
    for (int i = a.length / 2 - 1; i >= 0; i--) swaps += siftDown(a, a.length, i);
    return swaps;
}

Both produce [1, 3, 2, 5, 9, 8] from [5, 3, 8, 1, 9, 2] with 4 swaps, but their worst cases differ. Sift-up costs up to the node’s depth, and most nodes are deep: half of them are leaves at depth about log n. Sift-down costs up to the node’s height, and most nodes are low: half have height 0, a quarter height 1, an eighth height 2. The total is n × (1/4 + 2/8 + 3/16 + ...), which is less than n. The Java file measures it on a strictly decreasing array of 2^16 - 1 = 65535 values, the worst case for both: insertion makes 917,506 swaps (about 14n), bottom-up makes 65,519 (exactly n - 16). Use bottom-up whenever all elements are known in advance.

Heap sort

Build a max-heap bottom-up, then repeatedly swap the root (the maximum) with the last element of the unsorted part, shrink that part by one and sift the new root down. The array fills with the largest values from the back.

static void siftDownMax(int[] a, int n, int i) {
    while (true) {
        int largest = i, l = left(i), r = right(i);
        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == i) return;
        swap(a, i, largest);
        i = largest;
    }
}

static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDownMax(a, n, i);
    for (int end = n - 1; end > 0; end--) {
        swap(a, 0, end);
        siftDownMax(a, end, 0);
    }
}

It runs in O(n log n) time in every case with O(1) extra space, but it is not stable and its memory access jumps around, so library sorts usually prefer other algorithms.

Java’s PriorityQueue

java.util.PriorityQueue is exactly the array-backed binary min-heap above. offer/add and poll are O(log n), peek and size are O(1), building from a collection is O(n), while remove(Object) and contains are linear scans.

static List<Integer> pollAllMin(int[] values) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int v : values) pq.offer(v);
    List<Integer> out = new ArrayList<>();
    while (!pq.isEmpty()) out.add(pq.poll());
    return out;
}

For a max-heap, pass a reversed comparator:

static List<Integer> pollAllMax(int[] values) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    for (int v : values) pq.offer(v);
    List<Integer> out = new ArrayList<>();
    while (!pq.isEmpty()) out.add(pq.poll());
    return out;
}

Many later problems store pairs such as {distance, node} or {value, index}. Give the queue a comparator that decides the order, including ties:

static List<Integer> idsByPriority(int[][] tasks) {
    PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1]));
    for (int[] t : tasks) pq.offer(t);
    List<Integer> out = new ArrayList<>();
    while (!pq.isEmpty()) out.add(pq.poll()[1]);
    return out;
}

For tasks {3,10}, {1,7}, {3,2}, {2,5}, {1,9} it returns ids 7, 9, 5, 2, 10.

Where heaps appear in this section

Edge cases and pitfalls