---
title: Java Priority Queue
date: 2024-10-08
excerpt: An introduction to Java's PriorityQueue, its API, custom comparators, and the binary min-heap that powers it.
tags:
- Algorithm
- Java
- Queue
cover: https://assets.vluv.space/cover/Dev/Algorithm/priority_queue.webp
updated: 2026-07-08 21:22:41
lang: en
i18n:
cn: /priority_queue
translation: 2
---
## Intro
`{java} 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 `{java} PriorityQueue` a great fit for workloads with frequent insertions and removals, such as graph algorithms and scheduling algorithms.
This post covers how to use `{java} 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 `{java} null` elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in `{java} 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.
>
## Usage
### Creating a PriorityQueue
In Java, use the `{java} PriorityQueue` class to create a priority queue. The basic constructor looks like this:
```java
PriorityQueue queue = new PriorityQueue<>();
```
### Methods
- `{java} 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
- `{java} 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
- `{java} peek()`: returns the highest-priority element (the smallest one) without removing it. Returns null if the queue is empty.
- `{java} 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
- `{java} clear()`: removes all elements from the priority queue
- `{java} contains(Object o)`: checks whether the queue contains a given element
- `{java} remove(Object o)`: removes the specified element from the queue, returning true if it was present and false otherwise
- ......
#### Usage Examples
```java
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue 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 `{java} 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
```java
import java.util.PriorityQueue;
// Define the task class
class Task implements Comparable {
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 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();
}
}
}
```
```shell
Task scheduling started...
Executing: System Update with priority 1
System 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 0
Emergency Task execution finished.
Executing: Backup with priority 3
Backup execution finished.
Executing: User Report Generation with priority 4
User Report Generation execution finished.
All tasks completed.
```
> [!example] Application Scenarios
>
> - **Emergency rooms**: in a hospital ER, patients are triaged by severity, and critical patients get treated first. A priority queue can manage the order in which doctors and nurses see patients.
> - **Network routing**: in computer networks, priority queues manage packet flow. High-priority packets like voice and video data can take precedence over low-priority data like email and file transfers.
> - **Online marketplaces**: in an online marketplace, a priority queue can manage product delivery to customers. High-priority orders can be fulfilled ahead of standard shipping orders.
## 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.
```shell
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](https://leetcode.cn/problems/merge-k-sorted-lists/description/)
- [347. Top K Frequent Elements](https://leetcode.cn/problems/top-k-frequent-elements/description/)
- ...