Priority queue: PriorityQueue with a heap

A priority queue gives up the “first in, first out” rule of an ordinary queue. Each element carries a priority, and each time the highest-priority one comes out. A hospital emergency room, an operating system’s process scheduler and Dijkstra’s algorithm all use this. Last week you saw the binary heap as a data structure. This week we use it as an implementation of an abstract data type (ADT) and get to know Java’s ready-made PriorityQueue class.

Three kinds of questions come from this topic in the exam:

1. Tracing: “Insert these elements, do deleteMin twice, write the array.”
2. “What is printed?”: short code with PriorityQueue. The biggest trap is System.out.println(pq).
3. Application + Big-O: “find the k-th largest”, “merge k lists”, which heap and which complexity.

The priority queue ADT

The operations:

Why a heap? Compare with the alternatives:

AVL gives the same Big-O but deals with pointers and does rotations. A heap is a single array, with no pointers, and the code is short. This is the standard choice for a priority queue.

Reminder: the 1-indexed min-heap

The notation used by the textbook: the root is array[1], the children of the node at index i are 2i and 2i+1, and its parent is i/2. The heap-order rule: every parent is less than or equal to its children.

insert (percolate up): Put the element at the end of the array. While it is smaller than its parent, swap it with the parent.

deleteMin (percolate down): Remove the root. Move the last element to the root. While it is larger than its smaller child, swap it with the smaller child.

Example: insert 10, 4, 7, 1, 8, 3 into an empty heap.

insert 10 -> [10]
insert 4  -> [4, 10]
insert 7  -> [4, 10, 7]
insert 1  -> [1, 4, 7, 10]
insert 8  -> [1, 4, 7, 10, 8]
insert 3  -> [1, 4, 3, 10, 8, 7]

The final state as a tree:

          1
        /   \
       4     3
      / \   /
    10   8 7

Now two deleteMin operations:

deleteMin 1 -> [3, 4, 7, 10, 8]
deleteMin 3 -> [4, 8, 7, 10]

Let’s open up the second. 3 is removed, and the last element 8 comes to the root. The children are 4 and 7, the smaller is 4, and 4 < 8, so swap. 8 is now at index 2, and its only child is 10 (index 4). 10 > 8, stop.

PITFALL · swapping with the larger child in deleteMin. In a min-heap, when sinking you swap with the smaller child. If you swap with the larger, the smaller child remains smaller than its new parent and the heap rule breaks.

PriorityQueue in Java

java.util.PriorityQueue<E> is a binary heap. There are two differences: the array is 0-indexed (parent (i-1)/2, children 2i+1, 2i+2) and it is a min-heap by default.

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[]{5, 1, 8, 3, 2}) pq.offer(x);
System.out.println(pq);            // the internal array!
for (int x : pq) System.out.print(x + " ");
System.out.println();
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");

[1, 2, 8, 5, 3]
1 2 8 5 3 
1 2 3 5 8 

PITFALL · println(pq) is not sorted. toString() and the for-each loop walk the heap’s internal array in order. Only the first element is guaranteed to be the smallest. If you want sorted output, use a poll() loop. In the exam, writing [1, 2, 3, 5, 8] loses the points.

Max-heap and Comparator

For a max-heap, give a reverse comparator:

PriorityQueue<Integer> mx = new PriorityQueue<>(Collections.reverseOrder());
for (int x : new int[]{5, 1, 8, 3, 2}) mx.offer(x);
System.out.println(mx.peek() + " " + mx);

8 [8, 3, 5, 1, 2]

Give a Comparator for your own ordering rule. By length, and alphabetical if equal:

PriorityQueue<String> ps = new PriorityQueue<>(
    Comparator.comparingInt(String::length)
              .thenComparing(Comparator.naturalOrder()));
for (String s : new String[]{"pear","fig","apple","kiwi","date","plum"})
    ps.offer(s);
while (!ps.isEmpty()) System.out.print(ps.poll() + " ");

fig date kiwi pear plum apple 

It can also be written with a lambda: new PriorityQueue<>((a, b) -> b - a) gives a max-heap. But b - a can overflow with very large numbers; Integer.compare(b, a) is safer.

PITFALL · PriorityQueue is not stable. Two elements with equal priority do not have to come out in insertion order. If you want FIFO, add a second rule to the Comparator: an insertion sequence number or the name.

Application 1: k-th largest and k smallest

Three ways to find the k-th largest of n elements:

The third also works on a data stream: you do not need to know the data in advance, and the memory is $O(k)$. The idea: the heap holds the k largest elements so far. The root is the smallest of them. When a new element arrives, add it, and if the size exceeds k, discard the root.

static int kthLargest(int[] a, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int x : a) {
        pq.offer(x);
        if (pq.size() > k) pq.poll();
    }
    return pq.peek();
}

Trace for {7, 2, 9, 4, 11, 5, 3} and k = 3:

read 7  -> {7}
read 2  -> {2,7}
read 9  -> {2,7,9}
read 4  -> {2,4,7,9}  size 4 > 3, discard 2 -> {4,7,9}
read 11 -> {4,7,9,11} discard 4 -> {7,9,11}
read 5  -> {5,7,9,11} discard 5 -> {7,9,11}
read 3  -> {3,7,9,11} discard 3 -> {7,9,11}
answer peek = 7

The symmetric rule: a max-heap for the k smallest, a min-heap for the k largest. The root of the heap is the “gatekeeper”; you compare each candidate for entry with it.

Application 2: merging k sorted lists

In merge sort you know how to merge two lists. With k lists, at each step you need to find the smallest of the k heads. A heap does this: put the first element of each list into the heap. Whichever list the element you polled came from, add the next element of that list.

// heap element: {value, listNo, index}
PriorityQueue<int[]> pq =
    new PriorityQueue<>((p, q) -> Integer.compare(p[0], q[0]));
for (int i = 0; i < lists.size(); i++)
    if (!lists.get(i).isEmpty())
        pq.offer(new int[]{lists.get(i).get(0), i, 0});
List<Integer> out = new ArrayList<>();
while (!pq.isEmpty()) {
    int[] t = pq.poll();
    out.add(t[0]);
    int j = t[2] + 1;
    if (j < lists.get(t[1]).size())
        pq.offer(new int[]{lists.get(t[1]).get(j), t[1], j});
}

The output for [1,5,9], [2,6], [3,4,10]:

[1, 2, 3, 4, 5, 6, 9, 10]

The heap never has more than k elements. For N elements in total the time is $O(N \log k)$. External sorting, which sorts large files in pieces and merges them, is based on this idea.

Application 3: scheduling and event simulation

Job scheduling: The operating system keeps waiting jobs by priority. The highest-priority job runs each time. In the Comparator, priority first, and if equal, name or arrival order:

record Job(String name, int prio) {}
PriorityQueue<Job> jq = new PriorityQueue<>(
    Comparator.comparingInt(Job::prio).thenComparing(Job::name));
jq.offer(new Job("C", 2)); jq.offer(new Job("A", 3));
jq.offer(new Job("D", 1)); jq.offer(new Job("B", 1));
while (!jq.isEmpty()) System.out.print(jq.poll().name() + " ");

B D C A 

Event-driven simulation: Imagine simulating a bank counter. Instead of advancing second by second, you put the events (“customer arrived”, “customer left”) into a min-heap by their times. At each step you pull the earliest event, and the clock jumps directly to that moment. An event can create new events: when an “arrived” event is processed, a “left” event is added at the service end time. Let three customers arrive at t = 0, 1, 2, with one counter and a service time of 4 minutes:

t=0  arrive0  -> leave0 event added at t=4
t=1  arrive1  -> the counter is busy until 4, leave1 at t=8
t=2  arrive2  -> leave2 at t=12
t=4  leave0
t=8  leave1
t=12 leave2

If the number of events is E, the simulation takes $O(E \log E)$, however long the simulated time is.

Common mistakes

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[]{5, 1, 8, 3, 2}) pq.offer(x);
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[]{5, 1, 8, 3, 2}) pq.offer(x);
System.out.println(pq);

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int x : new int[]{5, 1, 8, 3, 2}) pq.offer(x);
pq.poll(); pq.poll();
System.out.println(pq.peek() + " " + pq.size());

PriorityQueue<String> pq = new PriorityQueue<>(
    Comparator.comparingInt(String::length)
              .thenComparing(Comparator.naturalOrder()));
for (String s : new String[]{"pear","fig","apple","kiwi","date","plum"})
    pq.offer(s);
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");

PriorityQueue<Integer> m = new PriorityQueue<>();
m.offer(6); m.offer(2); m.offer(9);
int a = m.poll();
m.offer(1); m.offer(7);
int b = m.poll();
System.out.println(a + " " + b + " " + m.peek() + " " + m.size());

7,2,9 → {2,7,9}
add 4 → {2,4,7,9}, 2 is discarded → {4,7,9}
11 → {4,7,9,11}, 4 is discarded → {7,9,11}
5 → 5 is added and immediately discarded → {7,9,11}
3 → discarded in the same way → {7,9,11}

static int kthLargest(int[] a, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int x : a) {
        pq.offer(x);
        if (pq.size() > k) pq.poll();
    }
    return pq.peek();
}