Java's PriorityQueue

The ready-made heap

import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        minHeap.offer(40); minHeap.offer(10); minHeap.offer(30);
        System.out.println("smallest: " + minHeap.peek());
        System.out.println("poll " + minHeap.poll() + ", then " + minHeap.poll());

        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
        maxHeap.offer(40); maxHeap.offer(10); maxHeap.offer(30);
        System.out.println("biggest: " + maxHeap.poll());
    }
}

Output

smallest: 10
poll 10, then 30
biggest: 40

Your own priorities

For objects, give the PriorityQueue a Comparator (Module 9) that decides who comes first:

import java.util.Comparator;
import java.util.PriorityQueue;

class Task {
    String name;
    int urgency;      // bigger = more urgent
    Task(String name, int urgency) { this.name = name; this.urgency = urgency; }
}

class MostUrgentFirst implements Comparator<Task> {
    public int compare(Task a, Task b) {
        return Integer.compare(b.urgency, a.urgency);
    }
}

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Task> todo = new PriorityQueue<Task>(new MostUrgentFirst());
        todo.offer(new Task("reply to email", 2));
        todo.offer(new Task("fix server", 9));
        todo.offer(new Task("lunch", 5));
        while (!todo.isEmpty()) {
            Task t = todo.poll();
            System.out.println(t.urgency + " " + t.name);
        }
    }
}

Output

9 fix server
5 lunch
2 reply to email

Common mistake: Printing a PriorityQueue (or looping over it with for-each) does not show sorted order – you see the heap's internal array. Only poll() gives items in priority order.