Priority Queue Implementation

Ear­lier in we have seen Min-Heap and Max-Heap Imple­men­ta­tion. Pri­or­ity Queue is its built-in imple­men­ta­tion in Java.

In this arti­cle we will see how to per­form Min-Heap and Max-Heap using Pri­or­ity Queue.

Brief:

A pri­or­ity queue is an abstract data type where each ele­ment has a “pri­or­ity” assigned to it. So the ele­ment with the higher pri­or­ity is served before the other ele­ments. Click here to know in detail about max-Heap and min-Heap. (Source : Wiki)

 Return Type Method Descrip­tion boolean offer(E e) Inserts the spec­i­fied ele­ment into this pri­or­ity 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 num­ber of ele­ments in this collection. void clear() Removes all of the ele­ments from this pri­or­ity queue. boolean contains(Object o) Returns true if this queue con­tains the spec­i­fied element. Iterator iter­a­tor() Returns an iter­a­tor over the ele­ments in this queue. boolean remove(Object o) Removes a sin­gle instance of the spec­i­fied ele­ment from this queue, if it is present. Com­para­tor com­para­tor() Returns the com­para­tor used to order the ele­ments in this queue, or null if this queue is sorted accord­ing to the nat­ural order­ing of its elements.

Min-Heap using Pri­or­ity 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 Pri­or­ity Queue:

This gets bit tricky here. By default the Pri­or­ity Queue works as min-Heap. To imple­ment the max-Heap we need to change the way pri­or­ity queue works inter­nally by over­rid­ing the Com­para­tor.

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

Ref­er­ence : https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html