PriorityQueue ordering

Key points

• A PriorityQueue is a binary heap kept in an array. peek and poll always see the smallest element.
• Order comes from Comparable, or from a Comparator handed to the constructor.
• toString and iteration show heap layout, not sorted order. Only poll is ordered — drain it to sort.
• Want the largest first? Pass Comparator.reverseOrder(). Break ties by chaining thenComparing.
• offer and poll are O(log n), peek is O(1), but contains is O(n).
• Keep the k largest values with a size-bounded min-heap: add, then poll whenever the size passes k.

Example

import java.util.*;

public class Main {

    record Job(String name, int priority) {
        @Override public String toString() { return name + "/" + priority; }
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> min = new PriorityQueue<>(List.of(5, 1, 9, 3));
        System.out.println("heap toString     : " + min + "   (heap layout, NOT sorted)");
        StringBuilder order = new StringBuilder();
        while (!min.isEmpty()) order.append(min.poll()).append(" ");
        System.out.println("poll order        : " + order.toString().trim());

        PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
        max.addAll(List.of(5, 1, 9, 3));
        System.out.println("max-heap peek     : " + max.peek());

        PriorityQueue<Job> jobs = new PriorityQueue<>(
                Comparator.comparingInt(Job::priority).thenComparing(Job::name));
        jobs.add(new Job("email", 2));
        jobs.add(new Job("backup", 5));
        jobs.add(new Job("alert", 1));
        System.out.println("next job out      : " + jobs.poll());

        PriorityQueue<Integer> top3 = new PriorityQueue<>();
        for (int n : new int[]{7, 2, 9, 4, 11, 1}) {
            top3.add(n);
            if (top3.size() > 3) top3.poll();
        }
        System.out.println("3 largest kept    : " + new TreeSet<>(top3) + "   (size-bounded min-heap)");
        System.out.println("costs             : offer and poll O(log n), peek O(1)");
    }
}

A PriorityQueue is sorted on the way out, never on the inside.