PriorityQueue Class

PriorityQueue is a generic collection class that extends AbstractQueue class and implements the Queue interface. While Queue is a first-in, first-out(FIFO) queue of elements, the functionality of PriorityQueue has been enhanced.

PriorityQueue creates a priority-in, priority-out Queue i.e. its elements are sorted in an ascending order which is automatically provided by its default Comparator interface, and we can manually implement the Comparator interface to give a descending order to the elements of a PriorityQueue.

The general declaration of PriorityQueue

class PriorityQueue<E>

Where, E specifies the type of objects stored in the PriorityQueue, which grows and shrinks dynamically.

Important features of PriorityQueue

Ascending order of elements in a PriorityQueue can be changed by providing a custom Comparator to the constructor of PriorityQueue.
PriorityQueue's elements may appear out-of-order in the output or when you try to iterate over them by calling iterator() method. Hence, in order to access its element in an ascending order, poll() method is used(for more on this, see the example section of this article).
Duplicate elements are allowed to be stored in a PriorityQueue.

Constructors :

1) PriorityQueue()
This constructor creates an empty PriorityQueue of a particular type. Example -

PriorityQueue<Integer> arrL= new PriorityQueue<Integer>();

This constructor example creates an empty PriorityQueue to hold Integer objects.

2) PriorityQueue(Collection <? extends E>c)
This constructor creates a PriorityQueue initialized with the elements of Collection c. With a condition, that, Collection c holds similar type of objects as the type declared by the PriorityQueue.

PriorityQueue<Integer> arrL1 = new PriorityQueue<Integer>():
PriorityQueue<Integer> arrL2 = new PriorityQueue<Integer>(arrL1);

This constructor example creates a PriorityQueue arrL2 initialized with the elements of a PriorityQueue arrL1. Both PriorityQueue hold Integer objects.

3) PriorityQueue(Comparator<? super E> comp)
This constructor will create an empty PriorityQueue which is sorted according to the specified Comparator(comp) in constructor.

PriorityQueue<String> ts2 = new PriorityQueue<String>(new Comp());

Some important methods of PriorityQueue class

Methods	Description
boolean add(E e)	Inserts the element e at the end of an PriorityQueue.
void addFirst(E e)	Inserts the element e at the beginning of the PriorityQueue.
void addLast(E e)	Inserts the element e at the end of PriorityQueue.
E removeFirst()	Removes the first element of the PriorityQueue.
E removeLast(E e)	Removes the last element of the PriorityQueue.
boolean offer(E e)	Inserts the element e in the PriorityQueue.
E peek()	Returns the head(first) element of the PriorityQueue, without removing it.
E poll()	Returns and removes the head(first) element of the PriorityQueue.
int size()	Returns the total number of elements in an ArrayList.
void clear()	Removes all of the elements from the ArrayList
E get(int index)	Returns the element at the specified index in an ArrayList.
E remove(int index)	Removes an element at a specified index in an ArrayList.
boolean remove(Object o)	Removes the first occurrence of an Object from the ArrayList, if it is present.
Object[] toArray()	Returns an Object array containing all the elements of an ArrayList.
Iterator iterator()	Returns an Iterator to iterate over elements of an ArrayList.
ListIterator listIterator()	Returns a ListIterator to iterate over elements of an ArrayList.

Example of PriorityQueue-:

In this program we have created an PriorityQueue to hold Integer objects by adding and removing some elements from it by using the offer() and add() methods of PriorityQueue class, and then we will iterate over its elements by calling its iterator() method.

Note: PriorityQueue's elements may appear out-of-order in the output or when you try to iterate over them by calling iterator() method.

//Java - Creating a PriorityQueue and iterating over its elements
 

import java.util.*;

public class PriorityQueue1 
{
public static void main(String... ar)
{
    
//Passing an object of implementer of Comparator Interface
PriorityQueue<Integer> priorityQ= new PriorityQueue(new PriorityQueue1());

priorityQ.offer(4);
priorityQ.offer(1);
priorityQ.offer(5); // Offer method adds an object in the PriorityQueue
priorityQ.add(2);   // add() also adds an object in the PriorityQueue
priorityQ.add(3);

priorityQ.remove(3); // to remove 3 from the PriorityQueue


//Calling the iterator() method to iterate over the elements of PriorityQueue
Iterator itr = priorityQ.iterator();

System.out.print("Contents of PriorityQueue are : ");

while(itr.hasNext())
{
	System.out.print(itr.next() + " " );
}

System.out.println("\nSize of PriorityQueue after using poll() = "+ priorityQ.size());
}

}

Output is - :

Contents of PriorityQueue are : 1 2 5 4 
Size of PriorityQueue after using poll() = 4

Instead of calling the iterator() method to iterate over the elements of PriorityQueue, we can call the poll() method of PriorityQueue to access its element in an ascending order, which is automatically provided by the default Comparator of PriorityQueue.

Calling poll() method to access the elements of PriorityQueue in ascending order

In this program we will create an PriorityQueue to hold Integer objects and we will add/remove some elements from it and then we will access its elements in an ascending order by calling its poll() method.

import java.util.*;

public class PriorityQueue1
{
public static void main(String... ar)
{

PriorityQueue<Integer> priorityQ= new PriorityQueue<Integer>();

priorityQ.offer(4);
priorityQ.offer(1);
priorityQ.offer(5); // Offer method adds an object in the PriorityQueue
priorityQ.add(2);   // add() also adds an object in the PriorityQueue
priorityQ.add(3);



priorityQ.remove(3); // to remove 3 from the PriorityQueue

System.out.println("PriorityQueue contents may appear out-of-order : " + priorityQ);

System.out.print("PriorityQueue in an ascending ordering using poll() method : ");

//poll() returns & removes the first element of Queue or returns null, if Queue is empty
for( Integer i= priorityQ.poll(); i!=null; i=priorityQ.poll()) 
{
System.out.print( i + " ");
}

System.out.println("\nSize of PriorityQueue after using poll() = "+ priorityQ.size());
}

}

Output is - :

PriorityQueue contents may appear out-of-order : [1, 2, 5, 4]
PriorityQueue in an ascending ordering using poll() method : 1 2 4 5
Size of PriorityQueue after using poll() = 0

Program Analysis

Method add() and offer() are called to add the Integer objects to the PriorityQueue.
Method remove(Object o) is called to remove the Integer object(3) from the PriorityQueue
Contents of PriorityQueue are shown and they may appear jumbled or out-of-order.
Method poll() is used to access the elements of PriorityQueue in an ascending order. It returns and remove the first(smallest) element in an ascending order or it returns a null if PriorityQueue is empty.
Finally, size() method is called to show that there is no element left in PriorityQueue as poll() method removed all the elements one by one.

Implementing Comparator interface in PriorityQueue for descending order.

Here in the next example, we are implementing Comparator interface to create a PriorityQueue with its elements in a descending order, and next we will call the poll() method of PriorityQueue to extract its elements in descending order.

//Giving descending order to the elements in PriorityQueue by implementing the Comparator Interface


import java.util.*;

class PriorityQSort implements Comparator<Integer>
{

//Overriding Comparator's compare() method to give a descending ordering
public int compare(Integer one, Integer two) 
{
return(two-one);
}


public static void main(String... ar)
{

//Passing an object of implementer of Comparator Interface
PriorityQueue<Integer> pq= new PriorityQueue<Integer>(new PriorityQSort()); 

pq.offer(4);
pq.offer(1);
pq.offer(5); // Offer method adds an object in the PriorityQueue
pq.add(2);   // add() also adds an object in the PriorityQueue
pq.add(3);


pq.remove(3); // to remove 3 from the PriorityQueue

System.out.println("Content of PriorityQueue without descending ordering" + pq);
System.out.println("Size of PriorityQueue = "+ pq.size());


System.out.println("Content of PriorityQueue with descending ordering : ");

//poll() returns & removes the first element of Queue or returns null, if Queue is empty
for( Integer i= pq.poll(); i!=null; i=pq.poll()) 
{
	System.out.print( i + " ");
}

}
}

Output is :

Content of PriorityQueue without descending ordering[5, 2, 4, 1]
Size of PriorityQueue = 4
Content of PriorityQueue with descending ordering : 5 4 2 1

A descending order is given to the elements in PriorityQueue by manually implementing its Comparator interface.

Please share this article -

< Prev

Next >

< Comparator for ordering

ArrayDeque Class >

Please Subscribe

Please subscribe to our social media channels for daily updates.

Notifications

Please check our latest addition

C#, PYTHON and DJANGO