|
Be the first user to complete this post
|
Add to List |
154. Priority Queue in Data Structure
Earlier in we have seen Min-Heap and Max-Heap Implementation. Priority Queue is its built-in implementation in Java.
In this article, we will see how to perform Min-Heap and Max-Heap using Priority Queue.
Brief:
A priority queue is an abstract data type where each element has a “priority” assigned to it. So the element with the higher priority is served before the other elements. Click here to know in detail about max-Heap and min-Heap. (Source: Wiki)
| Return Type | Method | Description |
| boolean | offer(E e) | Inserts the specified element into this priority queue. |
| E | peek() | Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty. |
| E | poll() | Retrieves and removes the head of this queue, or returns null if this queue is empty. |
| int | size() | Returns the number of elements in this collection. |
| void | clear() | Removes all of the elements from this priority queue. |
| boolean | contains(Object o) | Returns true if this queue contains the specified element. |
| Iterator<E> | iterator() | Returns an iterator over the elements in this queue. |
| boolean | remove(Object o) | Removes a single instance of the specified element from this queue, if it is present. |
| Comparator<? super E> | comparator() | Returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the natural ordering of its elements. |
Min-Heap using Priority Queue:
Output:
Output: [1, 4, 2, 9, 6, 3, 8] Min Element in the Priority Queue: 1 Min Element in the Priority Queue: 2 Min Element in the Priority Queue: 3 Priority Queue Size: 4
Max-Heap using Priority Queue:
This gets a bit tricky here. By default, the Priority Queue works as min-Heap. To implement the max-Heap we need to change the way the priority queue works internally by overriding the Comparator.
Output:
Output: [9, 6, 8, 1, 4, 2, 3] Max Element in the Priority Queue: 9 Max Element in the Priority Queue: 8 Max Element in the Priority Queue: 6 Priority Queue Size: 4
Reference : https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html