PriorityQueue is a class in the Java Collections Framework that provides an implementation of the Queue interface. A priority queue is a data structure that stores a collection of elements and returns the elements in a particular order. In a priority queue, the elements are retrieved in order of their priority, which is typically determined by a comparison function that is defined on the elements.
PriorityQueue in Java
The PriorityQueue class in Java implements a priority queue using a heap data structure. A heap is a binary tree-based data structure in which the parent node has a priority greater than or equal to the priority of its children. In a max-heap, the highest priority element is always the root of the tree, and in a min-heap, the lowest priority element is always the root of the tree.
In Java, PriorityQueue uses a min-heap by default. This means that the element with the lowest priority will be the first one returned when using the peek() or poll() methods. However, you can create a max-heap by passing a custom comparator function to the constructor of the PriorityQueue.
Creating a PriorityQueue
You can create a PriorityQueue in Java by using the constructor that takes no arguments or by passing an initial capacity and a comparator function. Here’s an example of creating a PriorityQueue with a capacity of 10 and a custom comparator that compares elements based on their length:
PriorityQueue pq = new PriorityQueue<>(10, Comparator.comparingInt(String::length));
Adding and Removing Elements
To add an element to a PriorityQueue, you can use the add() or offer() method. Both methods add the element to the queue and return true if the operation was successful. If the queue is full and the element cannot be added, these methods will return false.
To remove an element from a PriorityQueue, you can use the poll() method, which removes and returns the element with the lowest priority. If the queue is empty, poll() returns null. If you want to retrieve the element without removing it, you can use the peek() method, which returns the element with the lowest priority without removing it from the queue.
PriorityQueue pq = new PriorityQueue<>();
pq.add("apple");
pq.add("banana");
pq.add("orange");
String first = pq.poll(); // returns "apple"
String second = pq.poll(); // returns "banana"
String third = pq.poll(); // returns "orange"
Iterating over a PriorityQueue
You can use a for-each loop or an iterator to iterate over a PriorityQueue. However, the order in which the elements are returned is not guaranteed to be in any particular order.
PriorityQueue pq = new PriorityQueue<>();
pq.add("apple");
pq.add("banana");
pq.add("orange");
for (String fruit : pq) {
System.out.println(fruit);
}
Output:
apple
banana
orange
Conclusion
The PriorityQueue class in Java is a useful implementation of a priority queue that uses a min-heap data structure. It provides methods for adding, removing, and iterating over elements in the queue, as well as the ability to define a custom priority order using a comparator function. PriorityQueue is a useful tool for any application that requires the ordering of elements based on priority.
