Heaps in Java

In a hospital emergency room, patients aren't seen in the order they arrive. The most urgent case is always seen next, and when a new patient comes in with a more serious problem, they move ahead of others. The staff don't sort the whole waiting list every time; they only need to know who is most urgent right now. A heap is the data structure built for exactly that: it always gives you the smallest (or largest) item instantly, and adding or removing an item is cheap. In this lesson, you will learn how a heap is stored in an array, build a min-heap in Java with add and poll, and use the JDK's PriorityQueue.

What Is a Heap?

A heap in Java (as a data structure, not the JVM's memory area) is a complete binary tree that is used to keep the smallest or largest element at the top, by following the heap property:

• Min-heap: every parent is less than or equal to its children, so the minimum is at the root.
• Max-heap: every parent is greater than or equal to its children, so the maximum is at the root.

Complete means every level is full except possibly the last, which fills from the left. Because of that, a heap fits perfectly into an array with no gaps and no links.

Note that a heap is not sorted. Siblings can be in any order; only the parent-child rule holds.

A Tree Stored in an Array

The Two Operations

• add (sift up): put the new value at the end of the array, then swap it with its parent while it is smaller than the parent.
• poll (sift down): take the root (the minimum), move the last element to the root, then swap it with its smaller child while it is larger than that child.

Both walk at most one path from the root to a leaf, so both are O(log n).

A Min-Heap in Java

Let's see a min-heap of urgency levels (1 is the most urgent) with add, peek and poll.

import java.util.Arrays;
 
public class MinHeap {
    private int[] a = new int[8];
    private int size = 0;
 
    void add(int value) {
        if (size == a.length) a = Arrays.copyOf(a, size * 2);
        a[size] = value;
        int i = size++;
        while (i > 0 && a[i] < a[(i - 1) / 2]) {       // sift up
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }
 
    int peek() {
        if (size == 0) throw new IllegalStateException("empty");
        return a[0];
    }
 
    int poll() {
        int min = peek();
        a[0] = a[--size];                              // last goes to the top
        int i = 0;
        while (true) {                                 // sift down
            int left = 2 * i + 1, right = left + 1, smallest = i;
            if (left < size && a[left] < a[smallest]) smallest = left;
            if (right < size && a[right] < a[smallest]) smallest = right;
            if (smallest == i) break;
            swap(i, smallest);
            i = smallest;
        }
        return min;
    }
 
    private void swap(int x, int y) {
        int t = a[x];
        a[x] = a[y];
        a[y] = t;
    }
 
    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(a, size));
    }
 
    public static void main(String[] args) {
        MinHeap heap = new MinHeap();
        for (int v : new int[] {9, 3, 5, 14, 10, 8}) {
            heap.add(v);
            System.out.println("add " + v + " -> " + heap);
        }
        System.out.print("poll order:");
        while (heap.size > 0) {
            System.out.print(" " + heap.poll());
        }
        System.out.println();
    }
}

add 9 -> [9]
add 3 -> [3, 9]
add 5 -> [3, 9, 5]
add 14 -> [3, 9, 5, 14]
add 10 -> [3, 9, 5, 14, 10]
add 8 -> [3, 9, 5, 14, 10, 8]
poll order: 3 5 8 9 10 14

Explanation:

1. Each add appends the value and sifts it up. Adding 3 puts it after 9, then swaps it with 9 because it is smaller than its parent, so 3 becomes the root. The other values are larger than their parents and stay where they land.
2. After all six adds, the array is [3, 9, 5, 14, 10, 8], the heap in the picture.
3. Each poll removes the root, moves the last value to the top and sifts it down. The values come out in sorted order: 3, 5, 8, 9, 10, 14.
4. Taking every element out of a heap like this is heap sort: O(n log n), in place when done inside the same array.

PriorityQueue: The JDK's Heap

You rarely build a heap by hand. java.util.PriorityQueue is a min-heap stored in an array, exactly like MinHeap, and it works with any type and any Comparator.

import java.util.Comparator;
import java.util.PriorityQueue;
 
public class Emergency {
    record Patient(String name, int urgency) {}
 
    public static void main(String[] args) {
        PriorityQueue<Patient> queue = new PriorityQueue<>(
                Comparator.comparingInt(Patient::urgency));
        queue.add(new Patient("Navika", 3));
        queue.add(new Patient("Srihitha", 1));
        queue.add(new Patient("Advitha", 2));
 
        while (!queue.isEmpty()) {
            System.out.println("see " + queue.poll());
        }
 
        PriorityQueue<Integer> maxHeap =
                new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.add(40);
        maxHeap.add(95);
        maxHeap.add(72);
        System.out.println("highest mark: " + maxHeap.peek());
    }
}

see Patient[name=Srihitha, urgency=1]
see Patient[name=Advitha, urgency=2]
see Patient[name=Navika, urgency=3]
highest mark: 95

Explanation: the comparator makes the queue order patients by urgency, so Srihitha (1) is seen first. Passing Comparator.reverseOrder() turns PriorityQueue into a max-heap. See "Queue Interface and PriorityQueue in Java" for its other methods.

Complexity

Interview Corner

Practice

1. Easy: Change MinHeap into a max-heap by flipping the comparisons. Check that poll returns values from largest to smallest.
2. Harder: Using a PriorityQueue<Integer> as a min-heap of size 3, find the three highest marks in {56, 91, 47, 88, 73, 95, 62}.

Key Takeaways