A PriorityQueue is a special type of queue that orders elements based on their priority, rather than the order in which they were added. It is part of the java.util package and is a useful class when you need to process elements based on their priority.
Unlike a regular queue where elements are processed in the order they arrive (FIFO—First In, First Out), a PriorityQueue orders elements according to their natural order or according to a comparator you provide. This means the element with the highest priority is always dequeued first, rather than the element that arrived first.
Features
- No guarantee of FIFO order: Elements are dequeued based on their priority, not the order of insertion.
- Automatic sorting: The queue keeps elements sorted either using their natural ordering (like numbers or strings) or using a custom comparator.
- Null values not allowed: You cannot insert
nullinto aPriorityQueue, as it cannot be compared. - Unbounded queue: It can grow as needed to accommodate more elements.
Example
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import java.util.*; public class PriorityQueueExample { public static void main(String[] args) { // Create a PriorityQueue that orders elements in ascending order PriorityQueue<Integer> pq = new PriorityQueue<>(); // Adding elements to the PriorityQueue pq.offer(10); // Adds 10 to the queue pq.offer(20); // Adds 20 to the queue pq.offer(5); // Adds 5 to the queue pq.add(15); // Adds 15 to the queue (same as offer()) System.out.println("PriorityQueue after adding elements: " + pq); // Peeking at the top element (highest priority) System.out.println("Top element (highest priority): " + pq.peek()); // Removing elements from the PriorityQueue System.out.println("Removed element (poll): " + pq.poll()); // Removes the smallest element (5) // Checking the size of the PriorityQueue System.out.println("Size of the PriorityQueue after polling: " + pq.size()); // Checking if the PriorityQueue is empty System.out.println("Is the PriorityQueue empty? " + pq.isEmpty()); // Peeking at the new top element after poll() System.out.println("New top element after polling: " + pq.peek()); // Removing all elements and printing them one by one System.out.println("Removing all elements:"); while (!pq.isEmpty()) { System.out.println(pq.poll()); // Removes and prints each element } // Final check on whether the queue is empty System.out.println("Is the PriorityQueue empty after removing all elements? " + pq.isEmpty()); } } //Output PriorityQueue after adding elements: [5, 10, 20, 15] Top element (highest priority): 5 Removed element (poll): 5 Size of the PriorityQueue after polling: 3 Is the PriorityQueue empty? false New top element after polling: 10 Removing all elements: 10 15 20 Is the PriorityQueue empty after removing all elements? true |
Use Cases
- Scheduling tasks: If you have tasks with different priorities and want to process higher-priority tasks first.
- Graph algorithms: Priority queues are often used in algorithms like Dijkstra’s shortest path.
- Managing orders: If you’re managing a system where items need to be processed in order of priority.
- Huffman coding in data compression.
