Introduction
The Java util package provides a versatile data structure known as the PriorityQueue. This is essentially an implementation of a priority queue using a binary heap. By default, it works as a min-heap, but by passing a custom comparator, it can function as a max-heap. In this guide, we’ll explore the nuances of using the PriorityQueue for various types of objects.
Basics of PriorityQueue
A PriorityQueue is used when objects are supposed to be processed based on their priority. The elements of the priority queue are ordered according to their natural ordering or by a Comparator provided at the time of queue construction.
import java.util.PriorityQueue;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.add(5);
minHeap.add(20);
int top = minHeap.poll(); // Retrieves and removes the smallest number, which is 5
For Max-Heap
To transform the natural behavior of the PriorityQueue from a min-heap to a max-heap, you can pass a custom comparator:
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.add(10);
maxHeap.add(5);
maxHeap.add(20);
int top = maxHeap.poll(); // Retrieves and removes the largest number, which is 20
Handling Strings
For Strings, the natural order is lexicographic. However, you can also change the order using a custom comparator.
PriorityQueue<String> stringQueue = new PriorityQueue<>();
stringQueue.add("banana");
stringQueue.add("apple");
stringQueue.add("cherry");
String first = stringQueue.poll(); // "apple"
// For reverse lexicographic order:
PriorityQueue<String> reverseQueue = new PriorityQueue<>(Comparator.reverseOrder());
Custom Objects in PriorityQueue
To use custom objects in a PriorityQueue, you’ll need to either make the objects Comparable or provide an external Comparator.
Let’s consider a class Task:
public class Task {
int priority;
String description;
public Task(int priority, String description) {
this.priority = priority;
this.description = description;
}
public int getPriority() {
return priority;
}
// ... other getters and setters ...
}
If you want the PriorityQueue to order the tasks by their priority:
PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority));
taskQueue.add(new Task(5, "Do laundry"));
taskQueue.add(new Task(1, "Pay bills"));
taskQueue.add(new Task(3, "Buy groceries"));
Task nextTask = taskQueue.poll(); // Retrieves the task with priority 1: "Pay bills"
To reverse the order, you can use:
PriorityQueue<Task> taskQueueReverse = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority).reversed());