Java priority queues and heaps

Before you start

Java collections and comparators.

Always remove the smallest (or largest) item, and find the k largest values.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

A priority queue gives quick access to the item with the highest priority. Java's PriorityQueue is a binary min-heap: poll removes the smallest element in O(log n), and offer adds one in O(log n). Peeking at the smallest element is O(1). A heap is stored in an array, where the children of position i are at 2i + 1 and 2i + 2.

A reversed comparator turns it into a max-heap. To find the k largest values of a long stream, keep a min-heap of size k. For each new value, add it, and if the heap grows beyond k, remove the smallest. At the end the heap contains the k largest values, and the work is O(n log k), which is better than sorting all n values.

Code example

Java

import java.util.*;

class Main {
  public static void main(String[] args) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int v : new int[] {5, 1, 8, 3, 9, 2}) {
      minHeap.offer(v);
    }
    StringBuilder order = new StringBuilder();
    while (!minHeap.isEmpty()) {
      order.append(minHeap.poll()).append(' ');
    }
    System.out.println(order.toString().trim());

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    maxHeap.addAll(List.of(5, 1, 8, 3));
    System.out.println("largest " + maxHeap.peek());

    int k = 3;
    PriorityQueue<Integer> top = new PriorityQueue<>();
    for (int v : new int[] {7, 12, 3, 19, 5, 11, 2, 15}) {
      top.offer(v);
      if (top.size() > k) {
        top.poll();
      }
    }
    List<Integer> result = new ArrayList<>(top);
    Collections.sort(result, Collections.reverseOrder());
    System.out.println("top " + k + ": " + result);
  }
}

Output

1 2 3 5 8 9
largest 8
top 3: [19, 15, 12]

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1import java.util.*;

3class Main {

4 public static void main(String[] args) {

5 PriorityQueue<Integer> minHeap = new PriorityQueue<>();

6 for (int v : new int[] {5, 1, 8, 3, 9, 2}) {

7 minHeap.offer(v);

8 }

9 StringBuilder order = new StringBuilder();

10 while (!minHeap.isEmpty()) {

11 order.append(minHeap.poll()).append(' ');

12 }

13 System.out.println(order.toString().trim());

15 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

16 maxHeap.addAll(List.of(5, 1, 8, 3));

17 System.out.println("largest " + maxHeap.peek());

19 int k = 3;

20 PriorityQueue<Integer> top = new PriorityQueue<>();

21 for (int v : new int[] {7, 12, 3, 19, 5, 11, 2, 15}) {

22 top.offer(v);

23 if (top.size() > k) {

24 top.poll();

25 }

26 }

27 List<Integer> result = new ArrayList<>(top);

28 Collections.sort(result, Collections.reverseOrder());

29 System.out.println("top " + k + ": " + result);

30 }

31}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The default order makes a min-heap.	`—`	—
poll always removes the current smallest, so the values come out sorted.	`—`	—
Heap sort in miniature: n polls in sorted order.	`—`	1 2 3 5 8 9
A reversed comparator puts the largest value at the top.	`—`	1 2 3 5 8 9
peek looks at the top without removing it.	`—`	1 2 3 5 8 9 largest 8
When the heap exceeds k items, drop the smallest, which cannot be among the k largest.	`—`	1 2 3 5 8 9 largest 8
The heap kept 12, 15, and 19.	`—`	1 2 3 5 8 9 largest 8 top 3: [19, 15, 12]

Behind the scenes

How Java processes this code

The Java compiler produces bytecode. The JVM loads the class and invokes its main method.

Cost and common mistakes

offer and poll O(log n), peek O(1); the top-k method is O(n log k).

Iterating over a PriorityQueue does not give sorted order. Only poll returns elements in priority order.
PriorityQueue does not support fast removal of an arbitrary element or updating a priority in place.
Null elements are not allowed, and elements must be comparable or come with a Comparator.

Try it yourself

What does poll() return when the queue is empty?

Reveal answer and reasoning

null. Unlike remove(), which throws NoSuchElementException, poll returns null for an empty queue.