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.
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)
|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: [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 bit tricky here. By default the Priority Queue works as min-Heap. To implement the max-Heap we need to change the way priority queue works internally by overriding the Comparator.
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
Top Companies Interview Questions..-
If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.