Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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<E> 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<? super E> 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

You may also like...