Java Priority Queue
FREE
Overview
Java Priority Queue is a class that implements the Queue interface in Java. It is a special type of queue where each element is associated with a priority and is sorted based on its priority. The element with the highest priority is always at the front of the queue and is the first to be dequeued.
Priority Queues in Java are implemented using a heap data structure. This data structure allows for efficient insertion and removal of elements while maintaining the priority order. Time complexity to insert or remove an element from a heap is O(log n).
Introduction to Java Priority Queue
Java priority queue is a data structure that stores elements in a specific order based on their priority. It allows accessing the highest-priority element in the queue efficiently.
The priority queue utilizes a heap data structure to organize its elements. This indicates that the elements within the priority queue are arranged based on a comparator, which can be as basic as a regular number comparator.
Below is the hierarchy order of Priority Queue in Java.
A priority queue’s elements are ordered either by natural ordering (in which case the elements that are sorted first will be accessed first) or according to a comparator. In either case, the ordering of the elements represents their relative priority.
Declaration
where E is the type of elements held in this queue.
The class implements interfaces such as Serializable, Iterable<E>, Collection<E>, Queue<E>.
Important Points on Priority Queue
Here are a few important points on priority queue:
- It does permit a null value.
- A priority queue can’t be created for objects that are non-comparable based on any logic.
- Priority Queue is an unbound queue in Java as it has no fixed capacity, meaning it can grow dynamically as new elements are added to it.
- The least element with respect to ordering is known as the head of the queue.
- The PriorityQueue class in Java is not thread-safe by default.
- However, the PriorityBlockingQueue class can be used for thread-safe implementation of priority queue as it provides thread-safety and blocking operations for concurrent access.
- For methods like add and poll, O(log(n)) time is needed.
Java Priority Queue Constructors
Here are the following constructors in the Java priority queue:
PriorityQueue()
It creates a priority queue that has a default capacity of 11.
PriorityQueue(Collection<E> c)
This PriorityQueue constructor with a collection as argument creates a priority queue containing all the elements in the specified collection.
PriorityQueue(int initialCapacity)
It creates a priority queue that has the specified initial capacity.
PriorityQueue(int initialCapacity, Comparator<E> comparator)
It creates a priority queue that has a specified initial capacity, and the order of elements is according to the specified comparator.
PriorityQueue(PriorityQueue<E> pq)
It creates a priority queue having elements that are present in the specified priority queue given as argument.
PriorityQueue(SortedSet<E> s)
It creates a priority queue having elements that are present in the specified SortedSet as argument.
Java Priority Queue Examples
Output:
Explanation: In this example, basic operations are performed like adding the elements, iterating through the elements, removing the elements from the Priority queue, etc.
Custom Comparator in Priority Queue
In the examples above, the elements in the priority queue are retrieved according to the natural order. However, this ordering can be customized. For this, we will create our own comparator class as shown below.
Example:
Output:
Explanation:
- In this example, we have created a priority queue by passing CustomComparator as an argument. This class implements the Comparator interface.
- When the compare() method is overridden, it makes the head of the element as the largest number. It implies reverse ordering is in place.
- The method compareTo() is used for comparing the two values.
- Finally, we have printed the elements of the priority queue nums to show the order of elements inside it.
Priority Queue with Java Objects
In real-life applications, priority queues are generally used with java objects. In order to understand this more clearly, let’s take an example.
Output:
Explanation:
- In this example, the CustomerOrder class stores the order of customers. It implements the Comparable interface which decides on what basis the object should be ordered in the priority queue.
- The ordering is decided by the function compareTo() in which the line o.orderId > this.orderId ? 1 : -1 instructs the compiler that the order should be sorted on basis of orderId in the descending order.
- Thus the objects c1, c2 and c3 are stored on the basis of their orderId in decreasing order as you can see in the output.
Time Complexity of Major Priority Queue Operations
| Methods | Time complexity |
|---|---|
| poll | O(logn) |
| peek | O(1) |
| contains | O(n) |
| add | O(logn) |
| clear | O(1) |
| size | O(1) |
| toArray() | O(n) |
| offer | O(logn) |
Methods in Java Priority Queue
| Methods | Description |
|---|---|
| add(E e) | Inserts the specified element in the queue. |
| offer(E e) | Inserts the specified element in the queue. |
| clear() | Removes all of the elements from this queue. |
| size() | Returns the number of elements in this queue. |
| poll() | Retrieves and removes the head of this queue, or returns null (if empty). |
| peek() | Retrieves but does not remove the head of this queue, or returns null (if empty). |
| contains(element) | It searches for the specified elements and returns true if the element is found. |
| toArray() | It converts the priority queue to an array. |
| remove() | It removes and returns the head of the queue. Throws a NoSuchElementException if the queue is empty. |
| element() | It retrieves, but does not remove, the head of the priority queue, and throws NoSuchElementException if the queue is empty. |
Applications of Priority Queue
Here are a few applications of priority queue
- Dijkstra's shortest path algorithm: Priority queue is used to implement Dijkstra's algorithm to find the shortest path between two nodes in a graph.
- Huffman coding: A priority queue can be used to implement Huffman coding, which is used for data compression.
- Job scheduling: Jobs can be prioritized based on their importance and scheduled accordingly using a priority queue.
- Event-driven simulations: Priority queue can be used to simulate events in a certain order of their priority.
Conclusion
- When an object is supposed to be processed based on priority then a priority queue is used.
- The priority queue is based on a heap data structure. This means that the elements in the priority queue are ordered according to the natural order or by using a comparator.
- Declaration
- The PriorityQueue class in Java is not thread-safe by default.
- Priority Queue is an unbound queue in Java as it has no fixed capacity.
- Priority Queue can be used in algorithms such as Dijkstra's shortest path algorithm and Huffman encoding.