Heaps: weak ordering, sift up and sift down, PriorityQueue

← Back to the section

Quite often you don't need a full sort — you need one thing: pull out the largest (or smallest) element fast, again and again, adding new ones along the way. That is what a priority queue does. The efficient way to build one is a structure called a heap.

Weak ordering

A heap is a binary tree, but with a far milder rule than a search tree. There is only one condition: the key of any node is not smaller than the keys of its children (for a max-heap). This is called weak ordering: the largest element is guaranteed to sit on top, at the root, while the left-right order between nodes is not defined at all — a heap is not a sorted structure.

The relaxed rule is not a shortcoming but a fit for the task: only the maximum is needed, and it is always at hand, in the root. The heap spends no effort on full order, which is why insertion and extraction are cheap for it.

One more requirement: a heap is a complete tree, filled level by level from left to right with no gaps. That matters for how it is stored.

Stored in an array

A heap is not kept as a tree of nodes with references — it is laid into a plain array, level by level, and family ties are computed by arithmetic on the index:

• the children of node i are the cells 2i+1 and 2i+2;
• the parent of node i is the cell (i-1)/2.

No references and no node objects — an array and two formulas: less memory and faster access.

Sift up and sift down

Insertion (sift up, trickle up). The new element goes to the end of the array (the first free slot) and is "lifted": as long as it is greater than its parent, the two swap. The path runs from a leaf to the root, that is, the height of the tree, O(log N).

The same swap inside an array: the program inserts 30, 90, 70, 50 and prints the heap after every insertion.

live example

import java.util.Arrays;

public class HeapInsert {
    public static void main(String[] args) {
        int[] heap = new int[8];
        int size = 0;
        for (int value : new int[]{30, 90, 70, 50}) {
            int i = size++;
            heap[i] = value;
            while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
                int parent = (i - 1) / 2;
                int tmp = heap[i];
                heap[i] = heap[parent];
                heap[parent] = tmp;
                i = parent;
            }
            System.out.println("inserted " + value + ": " + Arrays.toString(Arrays.copyOf(heap, size)));
        }
    }
}

Extracting the maximum (sift down, trickle down). The maximum sits in the root and is taken from there. The hole in the root is filled with the last element of the array, which is then "pushed down": as long as it is smaller than the larger of its children, it swaps with that child. It sinks until the rule holds again. O(log N) as well.

So adding an element and taking the largest one both cost O(log N). That is why a heap is the filling of a priority queue, and through it of many algorithms — shortest path search, for one.

Heapsort

A full sorting algorithm grows out of the heap as well — heapsort. The idea is straightforward: dump every element into a heap, then take the maximum out one by one — they come out in descending order. Each extraction is O(log N) and there are N elements, hence O(N·log N), on par with quicksort.

A neat trick also makes heapsort an in-place sort: both the heap and the sorted result live in the same array. First the array is turned into a heap, then on every step the root (the maximum) swaps with the last element of the heap and the heap size shrinks — the extracted maxima pile up in the tail of the array already in order. Unlike quicksort, heapsort guarantees O(N·log N) even in the worst case.

How it works in Java

A heap is almost never written by hand, but you still have to know how it is built: the ready-made class has behaviour that surprises everyone who has not looked inside.

The reference implementation is PriorityQueue: exactly the binary heap described above, down to the index formulas and both swaps. There is one difference from our example — by default the heap is a min-heap: the smallest element by natural ordering ends up on top. If you need the maximum, pass a comparator to the constructor.

The complexity is predictable: offer (insertion) and poll (taking the top) are O(log n), because the element travels from a leaf to the root or back; peek (looking at the top without removing it) is O(1), it is simply cell zero of the array. The queue takes room for elements with a margin and grows on its own: a small array doubles, a large one grows by roughly half.

Two operations are expensive: contains and remove(Object) are O(n). The heap does not know where a particular value lies, so it has to scan the whole array. If you have to remove arbitrary elements often, a plain heap is the wrong structure.

And here is the main trap: iteration over a PriorityQueue is not sorted. Neither a for loop, nor toString, nor stream hand out elements in ascending order — they come in the order they lie in the array, where only weak ordering holds. Exactly one element is guaranteed: the one on top. The order appears on extraction: elements leave through poll strictly in ascending order.

live example

import java.util.List;
import java.util.PriorityQueue;

public class QueueOrder {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(List.of(5, 1, 9, 3));
        System.out.println(queue);        // [1, 3, 9, 5] — not sorted
        System.out.println(queue.peek()); // 1 — this one is guaranteed
        System.out.println(queue.poll() + ", " + queue.poll()); // 1, 3 — ascending
    }
}

Two more details people trip over: null cannot be put into the queue, and PriorityQueue is not thread-safe — for several threads there is PriorityBlockingQueue.

In short

• A heap is a complete binary tree with weak ordering: the largest element is in the root, but the tree as a whole is not sorted.
• It is stored in an array; node links are computed from the index (2i+1, 2i+2, (i-1)/2), with no references.
• Insertion (sift up) and extraction of the maximum (sift down) are both O(log N). That is the efficient base of a priority queue.
• Heapsort builds a heap and pulls maxima out of it — O(N·log N), in place, guaranteed even in the worst case.
• In PriorityQueue only peek, offer and poll are cheap; contains and remove(Object) are O(n), and iteration is never sorted.

What to read next

• Stacks and queues — the priority queue among its neighbours with restricted access.
• Advanced sorting — quicksort, the same O(N·log N) as heapsort.
• Weighted graphs — the heap inside shortest path search.
• Choosing a data structure — when a heap wins over a tree or a hash table.