Keyboard Shortcuts N Next post
P Previous post
S Save / unsave
R Read aloud
T Toggle theme
/ Focus search
Esc Close panels
🔥
Ready to read...
Java Java and Cryptography Mastery Series — Extended Java Programming Java Tutorial Module 19 - Advanced Collections and Concurrency

Java PriorityQueue with Min Heap and Max Heap Examples

Reviewed & accurate
AI Summary

Introduction

The Java PriorityQueue class joined the Java collections framework in Java 5 (2004) as part of JSR 166, the original java.util.concurrent package delivered by Doug Lea. It is an unbounded priority queue backed by a binary heap, a data structure that guarantees O(log n) insertion and removal while exposing the smallest (or, with a custom Comparator, the largest) element at the head in constant time. The class is not thread-safe by default; the thread-safe counterpart is PriorityBlockingQueue. The java priorityqueue implementation is a foundational data structure for scheduling, sorting, graph algorithms, and event-driven simulation.

For a Java learner, PriorityQueue is the right tool whenever you need to process elements in an order that is not the natural insertion order. The classic mistake is to use a sorted ArrayList or a TreeSet for this purpose, but neither gives the same constant-time access to the next element combined with logarithmic updates. This post walks through the binary heap mechanics, demonstrates both min-heap and max-heap configurations using the same PriorityQueue class, and shows a small task scheduler example that mirrors what real operating systems and job dispatchers do every day.

What is Java PriorityQueue?

The java priorityqueue class is an unbounded queue whose head is always the least element with respect to the ordering specified at construction. If you create it with the no-argument constructor, elements must implement Comparable and the natural ordering is used. If you supply a Comparator, that comparator decides which element comes out next. Two constructors wrap the same machinery: PriorityQueue() builds a default-capacity min-heap that grows as needed, while PriorityQueue(Comparator) lets you invert or customise the order without subclassing.

Conceptually, PriorityQueue belongs to the abstract data type known as a priority queue, a structure that supports three fundamental operations: insert (add or offer), peek (element or peek), and extract-min or extract-max (poll or remove). The PriorityQueue class also implements the Queue interface, so all the standard queue verbs are available. It is distinct from a sorted List because the heap invariant does not keep the whole array sorted; it keeps only the parent-child ordering relationships that guarantee the minimum (or maximum) is at index 0. It is also distinct from a TreeSet because PriorityQueue allows duplicate elements while TreeSet does not, and because PriorityQueue does not need a balanced tree to maintain its weaker invariant.

How Java PriorityQueue Works - Step by Step

Step 1: A binary heap is stored as an array. The element at index 0 is the root. The children of the element at index i are at 2i+1 and 2i+2, and the parent of the element at index j (with j greater than 0) is at (j-1)/2. A min-heap maintains the invariant that parent.compareTo(child) is less than or equal to 0 for every parent-child pair, which means the smallest element lives at index 0.

Step 2: Insertion with offer(e). The new element is appended at the end of the array, then sifted up: while its parent is greater (in a min-heap) than the new element, swap them. The cost is at most log2(n) swaps, giving an O(log n) insert. The array grows automatically when the capacity is exhausted, doubling its size like an ArrayList.

Step 3: Removal with poll(). The element at index 0 (the head) is removed and returned. The last element in the array is moved into index 0 and then sifted down: while the element is greater than its smallest child (in a min-heap), swap with that smallest child. The cost is again O(log n). Peek() just reads index 0 without any structural change, so it is O(1).

Step 4: To make a max-heap, pass Comparator.reverseOrder() or a custom lambda that flips the comparison. Internally, the same sift-up and sift-down routines use the comparator instead of Comparable, so the smallest with respect to reverseOrder is actually the largest with respect to natural order. This is how PriorityQueue supports both min-heap and max-heap using one implementation class.

Step 5: Iteration order is not sorted. PriorityQueue.iterator() traverses the underlying array in index order, which is not the priority order. To process elements in priority order, you must repeatedly call poll() until the queue is empty, or copy the elements into an ArrayList and sort that list. Iterating and acting in the same loop is a common bug because the iterator gives no priority guarantee.

Java Program for PriorityQueue

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

public class PriorityQueueDemo {
    static class Task implements Comparable<Task> {
        final int priority;
        final String name;
        Task(int priority, String name) {
            this.priority = priority;
            this.name = name;
        }
        @Override
        public int compareTo(Task other) {
            // higher priority value should run first = max-heap semantics
            return Integer.compare(other.priority, this.priority);
        }
        @Override
        public String toString() { return name + "(" + priority + ")"; }
    }

    public static void main(String[] args) {
        int[] data = {7, 3, 9, 1, 5, 2, 8};

        // Min-heap of Integers: head is the smallest
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int v : data) minHeap.offer(v);
        System.out.print("Min-heap poll order: ");
        while (!minHeap.isEmpty()) System.out.print(minHeap.poll() + " ");
        System.out.println();

        // Max-heap of Integers: head is the largest
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        for (int v : data) maxHeap.offer(v);
        System.out.print("Max-heap poll order: ");
        while (!maxHeap.isEmpty()) System.out.print(maxHeap.poll() + " ");
        System.out.println();

        // Task scheduler with custom Comparable (priority 5 runs before 1)
        PriorityQueue<Task> scheduler = new PriorityQueue<>();
        scheduler.offer(new Task(1, "log-rotate"));
        scheduler.offer(new Task(5, "alarm-flush"));
        scheduler.offer(new Task(3, "snapshot"));
        scheduler.offer(new Task(5, "metric-push"));
        System.out.println("Task execution order:");
        while (!scheduler.isEmpty()) System.out.println("  run " + scheduler.poll());
    }
}

Code Explanation - Line by Line

The Task inner class implements Comparable<Task> by inverting the natural integer comparison: compareTo returns Integer.compare(other.priority, this.priority), so a Task with priority 5 sorts before a Task with priority 1. This inversion is the classic idiom for turning a min-heap into a max-heap when the element type itself controls the ordering. The toString method renders the task in a readable form for the output, showing both the name and the priority value.

The main method constructs three independent PriorityQueue instances to demonstrate the three common usage modes. The first is a min-heap of Integer values built with the no-argument constructor, which uses the natural Comparable ordering of Integer. The offer(v) method inserts each value by sifting it up from the bottom of the underlying array. The poll() loop then drains the heap, printing elements in ascending order.

The second PriorityQueue is constructed with Comparator.reverseOrder(), a stateless Comparator that returns the reverse of natural ordering. The same offer/poll sequence now produces a descending output, demonstrating that the same PriorityQueue class serves as either a min-heap or a max-heap depending on the comparator. No subclass is needed, and the per-operation cost is identical.

The third PriorityQueue is the task scheduler. Because Task implements Comparable<Task> with inverted priority, tasks with priority 5 come out before priority 3, which comes before priority 1. When two tasks share the same priority (the two priority-5 tasks), their relative order is unspecified, reflecting the heap property that only guarantees parent versus child ordering, not sibling ordering. If you need a stable tie-breaker, add a sequence number field to the Task class.

Notice the iteration order hazard: if you replaced the poll loop with a forEach over the scheduler, you would see Task objects in array-index order, not in priority order. That is why poll() must be used to obtain a priority-sorted view, or alternatively the contents must be copied into a List and sorted explicitly.

Sample Input and Output

Input:
  data = {7, 3, 9, 1, 5, 2, 8}
  Tasks: (1, log-rotate), (5, alarm-flush), (3, snapshot), (5, metric-push)

Output:
  Min-heap poll order: 1 2 3 5 7 8 9
  Max-heap poll order: 9 8 7 5 3 2 1
  Task execution order:
    run alarm-flush(5)
    run metric-push(5)
    run snapshot(3)
    run log-rotate(1)

The first two lines confirm that the same PriorityQueue class can act as a min-heap or a max-heap purely by changing the comparator. The third block confirms that the task scheduler drains tasks in descending priority order, with same-priority tasks (alarm-flush and metric-push) appearing in arbitrary heap order. If you swapped the comparator to Comparator.naturalOrder() on Task (without the inverted compareTo), the priority-1 task would come out first because the natural ordering would rank smaller priority values as smaller.

Common Mistakes to Avoid

Mistake 1: Assuming iterator() returns elements in priority order. The iterator traverses the underlying array in index order, which is the heap-array order, not the priority order. If you need priority-order iteration, you must call poll() repeatedly until the queue is empty, or copy the elements into an ArrayList and sort that list. Many production bugs come from calling forEach on a PriorityQueue expecting sorted output.

Mistake 2: Mutating a Comparable field after the element is inserted. PriorityQueue does not re-heapify when a field used in compareTo changes. The element will remain in the wrong position, breaking the heap invariant for every subsequent poll. If you must update a priority, remove the element (which is O(n) by the way), modify it, and re-insert. The thread-safe PriorityBlockingQueue has the same caveat.

Mistake 3: Using a PriorityQueue as a Set. PriorityQueue allows duplicates; if your problem requires uniqueness, use a TreeSet or wrap the PriorityQueue in a HashSet check before inserting. The two structures serve different abstract data types and should not be conflated.

Mistake 4: Calling element() or remove() on an empty queue without try-catch. element() throws NoSuchElementException; peek() returns null. remove() throws; poll() returns null. For a producer-consumer scenario, prefer offer/peek/poll to avoid the exception overhead and to handle the empty case cleanly with null checks.

Real-World Applications

PriorityQueue is the workhorse of every scheduler in the Java ecosystem. java.util.concurrent.ScheduledThreadPoolExecutor stores its delayed tasks in a DelayedWorkQueue, which is a heap specialised for the ScheduledFutureTask type. The next task to fire is always at index 0, so the executor thread can wait for exactly the right delay before polling. The same pattern appears in Netty's HashedWheelTimer for time-bucketed scheduling.

Graph algorithms lean on PriorityQueue heavily. Dijkstra's shortest-path algorithm uses a min-heap keyed by tentative distance. A* search uses a min-heap keyed by f-score (the sum of cost-so-far and heuristic estimate). Prim's minimum-spanning-tree algorithm uses a min-heap keyed by edge weight. In all three cases, the algorithm updates a key and re-inserts, which is O(log n) per update; using a sorted list would be O(n) per update and O(n squared) overall.

Event-driven simulation frameworks use PriorityQueue to fire events in time-stamp order. Operating-system process schedulers and network-packet schedulers (the Linux Completely Fair Scheduler, network QoS class-based queues) are the same idea at scale. Online games and physics engines use PriorityQueue to fire collision events in time order so that the simulation is deterministic across runs.

Apache Lucene uses PriorityQueue to keep the top-N document scores during a search. The top-N with bounded heap pattern is the canonical case where PriorityQueue beats full sort: if you only need the top 10 of 10 million items, a min-heap of size 10 takes O(10 log 10) per insert instead of O(n log n) for full sort. The same pattern appears in Java 8 Stream.collect(Collectors.minBy) and in the Stream top-N collectors implemented by hand with a backing PriorityQueue.

Conclusion

The java priorityqueue class is an array-backed binary heap that delivers O(log n) insertion and removal with constant-time access to the minimum (or maximum) element. By supplying a custom Comparator, the same class serves as both a min-heap and a max-heap, which makes it suitable for task schedulers, graph algorithms, and top-N aggregations. To go further, study PriorityBlockingQueue for the thread-safe variant and DelayQueue for tasks that fire after a wall-clock delay.

Test Your Knowledge
How did you find this?

Comments

Join the discussion! Sign in with your Google or Blogger account, or comment as Anonymous - no account needed. For quick questions, also reach me on Telegram @cytestch.

Comments