Intro

PriorityQueue in Java is a special queue data structure built on a min-heap that supports priority ordering. It can order elements by their natural ordering or by a custom comparator. This makes PriorityQueue a great fit for workloads with frequent insertions and removals, such as graph algorithms and scheduling algorithms.

This post covers how to use PriorityQueue and takes a brief look at how it works under the hoodany deeper and I’m out of my depth

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).
…
Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe java.util.concurrent.PriorityBlockingQueue class.
https://docs.oracle.com/en/java/javase/22/docs/api/java.base/java/util/PriorityQueue.html

Usage

Creating a PriorityQueue

In Java, use the PriorityQueue class to create a priority queue. The basic constructor looks like this:

PriorityQueue<Type> queue = new PriorityQueue<>();

Methods

• add(E e): adds an element to the PriorityQueue. If the queue’s capacity is insufficient, it grows automatically. After the insertion, the queue adjusts its internal heap structure to preserve the min-heap property
• offer(E e): nearly identical to add, both insert an element into the queue, but when capacity is insufficient it returns false to signal failure instead of throwing an exception
• peek(): returns the highest-priority element (the smallest one) without removing it. Returns null if the queue is empty.
• poll(): removes and returns the highest-priority element (the smallest one), restoring the min-heap property by adjusting the heap. Unlike peek(), poll() modifies the queue
• clear(): removes all elements from the priority queue
• contains(Object o): checks whether the queue contains a given element
• remove(Object o): removes the specified element from the queue, returning true if it was present and false otherwise
• …

Usage Examples

import java.util.PriorityQueue;public class Main {    public static void main(String[] args) {        PriorityQueue<Integer> queue = new PriorityQueue<>();        queue.add(5);        queue.add(1);        queue.add(3);        System.out.println("queue.peek()：" + queue.peek()); // 1        System.out.println("queue.poll()：" + queue.poll()); // 1        System.out.println("queue.peek()：" + queue.peek()); // 3    }}

Custom Priorities

You can customize priorities by implementing the Comparator interface.

In an operating system’s task scheduling scenario, a priority queue can schedule tasks by priority. High-priority tasks get scheduled and executed first, while low-priority tasks wait until the high-priority ones finish.

Usage Example

import java.util.PriorityQueue;// Define the task classclass Task implements Comparable<Task> {    private String name;      // Task name    private int priority;     // Task priority; smaller number means higher priority    public Task(String name, int priority) {        this.name = name;        this.priority = priority;    }    // Get the task name    public String getName() {        return name;    }    // Get the task priority    public int getPriority() {        return priority;    }    // Define the comparison method, ordering by priority    @Override    public int compareTo(Task other) {        return Integer.compare(this.priority, other.priority); // Smaller priority value comes first    }    // Print task info    @Override    public String toString() {        return "Task{name='" + name + "', priority=" + priority + "}";    }}public class TaskScheduler {    public static void main(String[] args) {        // Create a priority queue for scheduling tasks        PriorityQueue<Task> taskQueue = new PriorityQueue<>();        // Add tasks to the queue        taskQueue.add(new Task("System Update", 1));  // High-priority task        taskQueue.add(new Task("Backup", 3));         // Low-priority task        taskQueue.add(new Task("Email Sync", 2));     // Medium-priority task        taskQueue.add(new Task("User Report Generation", 4)); // Even lower-priority task        // Schedule tasks: execute in priority order        System.out.println("Task scheduling started...\n");        int count = 1;        while (!taskQueue.isEmpty()) {            Task task = taskQueue.poll(); // Take and remove the highest-priority task            System.out.println("Executing: " + task.getName() + " with priority " + task.getPriority());            // Simulate a priority-0 task cutting in line while the second task runs            if (count == 2) {                Task emergencyTask = new Task("Emergency Task", 0); // A priority-0 task that jumps the queue                System.out.println("\n*** New task arrives: " + emergencyTask.getName() + " with priority " + emergencyTask.getPriority() + " ***\n");                taskQueue.add(emergencyTask); // The emergency task enters the queue            }            // Task execution logic            simulateTaskExecution(task);            count++;        }        System.out.println("\nAll tasks completed.");    }    // Simulate task execution    private static void simulateTaskExecution(Task task) {        try {            // Simulate execution time; assume each task takes 1 second            Thread.sleep(1000);            System.out.println(task.getName() + " execution finished.\n");        } catch (InterruptedException e) {            Thread.currentThread().interrupt();        }    }}

Task scheduling started...Executing: System Update with priority 1System Update execution finished.Executing: Email Sync with priority 2*** New task arrives: Emergency Task with priority 0 ***Email Sync execution finished.Executing: Emergency Task with priority 0Emergency Task execution finished.Executing: Backup with priority 3Backup execution finished.Executing: User Report Generation with priority 4User Report Generation execution finished.All tasks completed.

How It Works

PriorityQueue internally keeps its elements in an array structured as a min-heap, maintaining the heap property through array indices:

• The root sits at index 0.
• For each index i:
  • Left child: 2 * i + 1
  • Right child: 2 * i + 2
  • Parent: (i - 1) / 2

A binary heap is a special kind of complete binary tree, widely used to implement data structures like priority queues. It has two main properties:

• Structural property (complete binary tree):
  A binary heap is a complete binary tree, meaning every level is fully filled except possibly the last, whose nodes must be packed from left to right.
• Heap property (heap order):
  • Max-heap: every node’s value is greater than or equal to its children’s values, so the top element (the root) is the largest in the heap.
  • Min-heap: every node’s value is less than or equal to its children’s values, so the top element (the root) is the smallest in the heap.

  Min-heap example        2       / \      3   5     / \   \    6   8   10

Applications of Binary Heaps

Priority queues:

• Priority queue: usually implemented with a min-heap. The top element is always the minimum, allowing fast lookup, insertion, and removal of the best element.
• Heapsort: a sorting algorithm built on binary heaps. By repeatedly moving the largest or smallest element to the end of the heap, it eventually sorts the array. Heapsort runs in O(n log n) time and needs no extra storage.
• Graph algorithms: Dijkstra’s algorithm, Prim’s algorithm, and others repeatedly pick the best node from a set of candidates and update it

Practice

• 23. Merge K Sorted Lists
• 347. Top K Frequent Elements
• …