Heaps and Priority Queues

When you arrive at a hospital emergency room, you do not get treated in the order you arrived. A person with chest pain goes before a person with a sprained ankle, even if the sprain came in first. The staff always take the most urgent case next.

That is not a queue, because a queue serves the oldest first. It is a priority queue: every item has a priority, and the item with the highest priority leaves first. Task schedulers, "find the top 10" features, shortest-path algorithms and event simulations all rely on one.

The standard way to build a priority queue is a data structure called a heap. By the end of this article, you will know how a heap works inside, how to use Java's PriorityQueue, and the handful of patterns that interviewers love.

• What a priority queue is, and what a binary heap is.
• How a heap is stored in an array, and how insert and remove work.
• How to use PriorityQueue in Java, including max-heaps and custom comparators.
• How to solve k-th largest, top-K frequent and merge-K-sorted problems.
• How a heap differs from a binary search tree.

A binary heap is a binary tree with two properties.

1. Shape: it is a complete tree. Every level is full, except possibly the last, and the last level is filled from left to right. There are no gaps.
2. Order: the heap property. In a min-heap, every node is less than or equal to its children, so the smallest value is at the root. In a max-heap, every node is greater than or equal to its children, so the largest value is at the root.

A min-heap:          1        /   \       3     2      / \   /     7   4 5

Notice what the heap property does not say: it does not say the left child is smaller than the right child, or that each level is sorted. 3 and 2 are both below 1, and 3 > 2 sits on the left. Only the parent-child relation is ordered. That weaker rule is what makes heaps cheap to maintain.

Because the tree is complete, there are no holes, and we can store it in a plain array, level by level, with no pointers at all. With 0-based indexes, for the node at index i:

The heap above is stored as [1, 3, 2, 7, 4, 5]. Check: the node at index 1 (value 3) has children at indexes 3 and 4 (values 7 and 4), and its parent is at (1 - 1) / 2 = 0 (value 1). The root is always data[0], so peek is O(1).

1. Put the new value at the end of the array (the next free spot in the last level, which keeps the shape complete).
2. If it is smaller than its parent, swap them. Repeat until it is no longer smaller than its parent, or it reaches the root. This moving up is called sift up (or "bubble up").

1. Save the root (the minimum) to return it.
2. Move the last element of the array to the root. This keeps the shape complete, but the order may now be wrong at the top.
3. While the element is larger than one of its children, swap it with its smaller child. This moving down is called sift down.

Both operations walk along one root-to-leaf path. A complete tree with n nodes has height about log2(n), so both take O(log n) time.

Here is a complete MinHeap of ints, with a demo that prints the array after every step:

// File: Main.javaimport java.util.Arrays;public class Main {    static class MinHeap {        private int[] data = new int[4];        private int size;        void offer(int value) {            if (size == data.length) {                data = Arrays.copyOf(data, size * 2);            }            data[size] = value;            siftUp(size);            size++;        }        int peek() {            if (size == 0) {                throw new IllegalStateException("heap is empty");            }            return data[0];        }        int poll() {            if (size == 0) {                throw new IllegalStateException("heap is empty");            }            int min = data[0];            size--;            data[0] = data[size];            // move the last element to the root            if (size > 0) {                siftDown(0);            }            return min;        }        private void siftUp(int i) {            while (i > 0) {                int parent = (i - 1) / 2;                if (data[parent] <= data[i]) {                    break;                   // heap property restored                }                swap(parent, i);                i = parent;            }        }        private void siftDown(int i) {            while (true) {                int left = 2 * i + 1;                int right = left + 1;                int smallest = i;                if (left < size && data[left] < data[smallest]) {                    smallest = left;                }                if (right < size && data[right] < data[smallest]) {                    smallest = right;                }                if (smallest == i) {                    break;                   // no child is smaller                }                swap(i, smallest);                i = smallest;            }        }        private void swap(int a, int b) {            int temp = data[a];            data[a] = data[b];            data[b] = temp;        }        @Override        public String toString() {            return Arrays.toString(Arrays.copyOf(data, size));        }    }    public static void main(String[] args) {        MinHeap heap = new MinHeap();        for (int x : new int[] {5, 3, 8, 1, 2}) {            heap.offer(x);            System.out.println("offer " + x + " -> " + heap);        }        System.out.println("poll " + heap.poll() + " -> " + heap);        System.out.println("poll " + heap.poll() + " -> " + heap);        System.out.println("poll " + heap.poll() + " -> " + heap);    }}

offer 5 -> [5]offer 3 -> [3, 5]offer 8 -> [3, 5, 8]offer 1 -> [1, 3, 8, 5]offer 2 -> [1, 2, 8, 5, 3]poll 1 -> [2, 3, 8, 5]poll 2 -> [3, 5, 8]poll 3 -> [5, 8]

Follow the interesting steps:

Look at the array after the first poll: [2, 3, 8, 5]. The values are not in sorted order, but the heap property holds at every parent. That is all a heap promises.

You will almost never write your own heap in an interview or at work. Java provides java.util.PriorityQueue, a min-heap based on this exact design.

Default order is the natural ordering (smallest first). To change it, pass a comparator:

• Largest first: new PriorityQueue<>(Collections.reverseOrder()) or new PriorityQueue<>((a, b) -> Integer.compare(b, a)).
• Custom objects: new PriorityQueue<>(Comparator.comparingInt((Task t) -> t.priority).thenComparing(t -> t.name)).

// File: Main.javaimport java.util.Collections;import java.util.Comparator;import java.util.PriorityQueue;public class Main {    static class Task {        final String name;        final int priority;     // smaller number = more urgent        Task(String name, int priority) {            this.name = name;            this.priority = priority;        }    }    public static void main(String[] args) {        PriorityQueue<Integer> min = new PriorityQueue<>();        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());        for (int x : new int[] {5, 3, 8, 1, 2}) {            min.offer(x);            max.offer(x);        }        System.out.println("internal order of min: " + min + "  peek=" + min.peek());        StringBuilder fromMin = new StringBuilder();        while (!min.isEmpty()) {            fromMin.append(min.poll()).append(' ');        }        StringBuilder fromMax = new StringBuilder();        while (!max.isEmpty()) {            fromMax.append(max.poll()).append(' ');        }        System.out.println("polled from min: " + fromMin.toString().trim());        System.out.println("polled from max: " + fromMax.toString().trim());        PriorityQueue<Task> tasks = new PriorityQueue<>(                Comparator.comparingInt((Task t) -> t.priority).thenComparing(t -> t.name));        tasks.offer(new Task("write report", 2));        tasks.offer(new Task("fix bug", 1));        tasks.offer(new Task("email", 3));        tasks.offer(new Task("deploy", 1));        StringBuilder order = new StringBuilder();        while (!tasks.isEmpty()) {            Task t = tasks.poll();            order.append(t.name).append(" (").append(t.priority).append("); ");        }        System.out.println(order.toString().trim());    }}

internal order of min: [1, 2, 8, 5, 3]  peek=1polled from min: 1 2 3 5 8polled from max: 8 5 3 2 1deploy (1); fix bug (1); write report (2); email (3);

The first line is an important warning in disguise: printing a PriorityQueue or looping over it does not give sorted order. You see the internal heap array, which is only partly ordered, and it is an implementation detail. The only guaranteed way to get items in order is to poll them one at a time. The tasks come out by priority first, and when two have equal priority, by name, thanks to thenComparing.

Problem. Given an unsorted array, return its k-th largest element (counting duplicates). For [3, 2, 1, 5, 6, 4] and k = 2, the answer is 5.

Approach A, sorting. Sort and read position n - k. O(n log n) time.

Approach B, a heap of size k. Keep a min-heap that holds the k largest values seen so far. For each new value, add it. If the heap now has more than k items, remove the smallest. At the end, the heap holds the k largest values, and its minimum, the root, is the k-th largest.

It may feel backwards to use a min-heap to find the largest values, so think about what you need: you must be able to evict the weakest member of the club of k winners. The weakest winner is the smallest one, and a min-heap hands you exactly that in O(1).

Each of the n values costs O(log k), so the total is O(n log k) time and O(k) space. That beats sorting when k is much smaller than n, and works on a stream where you cannot store everything.

Problem. Return the k most frequent values in an array. For [1, 1, 1, 2, 2, 3] and k = 2, the answer is [1, 2].

Step 1: count frequencies with a HashMap (the pattern from Hashing). Step 2: keep a min-heap of size k, ordered by frequency, so the least frequent candidate is evicted whenever the heap grows too large. Total O(n + m log k) for m distinct values.

When two values have equal frequency the problem needs a tie-break rule. Here we output by decreasing frequency, and by increasing value when frequencies tie.

Problem. Merge k sorted arrays into one sorted array.

Merging two sorted lists is a simple two-pointer job (you did it in the arrays and linked-list articles). For k lists, the question at each step is "which of the k current front elements is smallest?" A min-heap answers that in O(log k). Put the first element of each list in the heap, along with which list it came from and its position. Poll the smallest, append it to the result, and push the next element from the same list. With N total elements, the time is O(N log k) and the heap holds at most k items.

// File: Main.javaimport java.util.Arrays;import java.util.HashMap;import java.util.Map;import java.util.PriorityQueue;public class Main {    static int kthLargest(int[] nums, int k) {        PriorityQueue<Integer> heap = new PriorityQueue<>();    // min-heap holding the k largest so far        for (int x : nums) {            heap.offer(x);            if (heap.size() > k) {                heap.poll();                                    // evict the smallest            }        }        return heap.peek();    }    static int[] topKFrequent(int[] nums, int k) {        Map<Integer, Integer> counts = new HashMap<>();        for (int x : nums) {            counts.merge(x, 1, Integer::sum);        }        // Weakest first: lower count, and for equal counts the larger value.        PriorityQueue<int[]> heap = new PriorityQueue<>(                (a, b) -> a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(b[0], a[0]));        for (Map.Entry<Integer, Integer> e : counts.entrySet()) {            heap.offer(new int[] {e.getKey(), e.getValue()});            if (heap.size() > k) {                heap.poll();            }        }        int[] result = new int[heap.size()];        for (int i = result.length - 1; i >= 0; i--) {          // strongest ends up first            result[i] = heap.poll()[0];        }        return result;    }    // Each heap entry is {value, which list, position in that list}.    static int[] mergeSorted(int[][] lists) {        int total = 0;        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));        for (int i = 0; i < lists.length; i++) {            total += lists[i].length;            if (lists[i].length > 0) {                heap.offer(new int[] {lists[i][0], i, 0});            }        }        int[] merged = new int[total];        int k = 0;        while (!heap.isEmpty()) {            int[] smallest = heap.poll();            merged[k++] = smallest[0];            int list = smallest[1];            int next = smallest[2] + 1;            if (next < lists[list].length) {                heap.offer(new int[] {lists[list][next], list, next});            }        }        return merged;    }    public static void main(String[] args) {        System.out.println(kthLargest(new int[] {3, 2, 1, 5, 6, 4}, 2));        System.out.println(kthLargest(new int[] {3, 2, 3, 1, 2, 4, 5, 5, 6}, 4));        System.out.println(kthLargest(new int[] {7}, 1));        System.out.println(Arrays.toString(topKFrequent(new int[] {1, 1, 1, 2, 2, 3}, 2)));        System.out.println(Arrays.toString(topKFrequent(new int[] {4, 4, 5, 5, 6}, 2)));        System.out.println(Arrays.toString(topKFrequent(new int[] {1}, 1)));        int[][] lists = {{1, 4, 7}, {2, 5, 8}, {0, 3, 6, 9}, {}};        System.out.println(Arrays.toString(mergeSorted(lists)));        System.out.println(Arrays.toString(mergeSorted(new int[][] {{}, {}})));    }}

547[1, 2][4, 5][1][0, 1, 2, 3, 4, 5, 6, 7, 8, 9][]

Dry run of kthLargest([3, 2, 1, 5, 6, 4], 2). The heap never holds more than 2 values:

The smallest of the two survivors, 5, is the second largest value. This is O(n log k). Two practical notes: peek() on an empty heap returns null (which would crash on unboxing), so we assume 1 <= k <= n. And you can also solve this in O(n) average time with a technique called quickselect, which we do not cover here.

Both are binary trees with an ordering rule, which is why people mix them up. They solve different problems.

If your question is "what is the next smallest item?", use a heap. If it is "is this value present?" or "what is the nearest value to x?", use a balanced search tree (Java's TreeSet or TreeMap).

Because a max-heap puts the largest element at the root, you can sort an array by building a max-heap in place in O(n), then repeatedly swapping the root with the last element of the heap and sifting down. It runs in O(n log n) time with O(1) extra space, but it is not stable and is usually slower in practice than the sorts in Searching and Sorting. It is more important as an idea than as a tool.

• Expecting sorted output from printing or iterating a PriorityQueue. Only poll gives the order.
• Writing b - a in a comparator. Use Integer.compare(b, a). This breaks on large positive and negative values.
• Using a max-heap when you need a min-heap, or the other way round, for top-K. To keep the k largest, use a min-heap of size k.
• Calling peek or poll on an empty queue and then unboxing the null. Check isEmpty().
• Putting mutable objects in the queue and changing their priority afterwards. The heap does not notice; remove and re-insert instead.
• Using remove(x) or contains(x) in a loop, which makes the code O(n^2).
• Forgetting null. PriorityQueue does not accept null elements.
• Ties. If equal priorities must be broken in a specific way (alphabetical, oldest first), add that rule to the comparator.
• Not stating the choice of k versus n. The O(n log k) approach shines when k is small. If k is close to n, sorting is as good.

PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);

// File: Main.javaimport java.util.PriorityQueue;public class Main {    public static void main(String[] args) {        PriorityQueue<Integer> heap = new PriorityQueue<>();        for (int x : new int[] {9, 4, 7, 1, 6}) {            heap.offer(x);            System.out.println("offer " + x + " -> " + heap);        }        System.out.println("poll " + heap.poll() + " -> " + heap);    }}

offer 9 -> [9]offer 4 -> [4, 9]offer 7 -> [4, 9, 7]offer 1 -> [1, 4, 7, 9]offer 6 -> [1, 4, 7, 9, 6]poll 1 -> [4, 6, 7, 9]

// File: Main.javaimport java.util.Arrays;import java.util.PriorityQueue;public class Main {    static long dist2(int[] p) {        return (long) p[0] * p[0] + (long) p[1] * p[1];    }    static int[][] kClosest(int[][] points, int k) {        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Long.compare(dist2(b), dist2(a)));   // farthest on top        for (int[] p : points) {            heap.offer(p);            if (heap.size() > k) {                heap.poll();                          // drop the farthest            }        }        int[][] result = new int[heap.size()][];        for (int i = result.length - 1; i >= 0; i--) {            result[i] = heap.poll();                  // farthest first, so fill from the back        }        return result;    }    public static void main(String[] args) {        int[][] points = {{3, 3}, {5, -1}, {-2, 4}, {1, 1}, {0, 2}};        for (int[] p : kClosest(points, 3)) {            System.out.println(Arrays.toString(p) + " d2=" + dist2(p));        }        System.out.println(kClosest(points, 0).length);    }}

[1, 1] d2=2[0, 2] d2=4[3, 3] d2=180

// File: Main.javaimport java.util.Collections;import java.util.PriorityQueue;public class Main {    static int lastStoneWeight(int[] stones) {        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());        for (int s : stones) {            heap.offer(s);        }        while (heap.size() > 1) {            int first = heap.poll();        // heaviest            int second = heap.poll();       // second heaviest            if (first != second) {                heap.offer(first - second); // what remains of the heavier one            }        }        return heap.isEmpty() ? 0 : heap.peek();    }    public static void main(String[] args) {        System.out.println(lastStoneWeight(new int[] {2, 7, 4, 1, 8, 1}));        System.out.println(lastStoneWeight(new int[] {5, 5}));        System.out.println(lastStoneWeight(new int[] {3}));        System.out.println(lastStoneWeight(new int[] {}));    }}

1030

// File: Main.javaimport java.util.Collections;import java.util.PriorityQueue;public class Main {    public static void main(String[] args) {        PriorityQueue<Integer> buggy = new PriorityQueue<>((a, b) -> b - a);        PriorityQueue<Integer> fixed = new PriorityQueue<>(Collections.reverseOrder());        for (int x : new int[] {Integer.MIN_VALUE, 1, 0}) {            buggy.offer(x);            fixed.offer(x);        }        System.out.println("buggy first: " + buggy.poll() + ", fixed first: " + fixed.poll());    }}

buggy first: 0, fixed first: 1

// File: Main.javaimport java.util.Collections;import java.util.PriorityQueue;public class Main {    static class MedianFinder {        private final PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());   // smaller half        private final PriorityQueue<Integer> high = new PriorityQueue<>();                             // larger half        void add(int num) {            low.offer(num);            high.offer(low.poll());              // keeps every value in low <= every value in high            if (high.size() > low.size()) {                low.offer(high.poll());          // rebalance so low is never smaller            }        }        double median() {            if (low.isEmpty()) {                throw new IllegalStateException("no numbers yet");            }            if (low.size() > high.size()) {                return low.peek();            }            return ((double) low.peek() + high.peek()) / 2;        }    }    public static void main(String[] args) {        MedianFinder finder = new MedianFinder();        StringBuilder out = new StringBuilder();        for (int x : new int[] {5, 15, 1, 3}) {            finder.add(x);            out.append(finder.median()).append(' ');        }        System.out.println(out.toString().trim());        MedianFinder big = new MedianFinder();        big.add(Integer.MAX_VALUE);        big.add(Integer.MAX_VALUE);        System.out.println(big.median());    }}

5.0 10.0 5.0 4.02.147483647E9

• Next: Searching and Sorting: Choose the Right Approach starts the algorithms module, and uses comparators just as you did here.
• Later uses: Shortest Paths and Topological Sorting uses a priority queue for Dijkstra's algorithm. Greedy Algorithms and Intervals uses heaps for scheduling.
• Practice habit: when a problem says "k largest", "k smallest", "k closest" or "most frequent k", start by asking which heap and what size.