Priority Queue using Java

Frequently used PriorityQueue Methods

add()

The add() method as the name suggests is used to add an element in the Priority Queue.

class PriorityQueueDemo {
    public static void main(String args[])
    {
        // Creating an empty priority queue.
        PriorityQueue<Integer> pQ = new PriorityQueue<Integer>();
 
        // Adding items to the pQueue using add() method.
        pQ.add(91);
        pQ.add(21);
 
    }
}

 

Time Complexity

O(log(N)), where ‘N’ is the number of elements in the priority queue.

 

Okay, now you have understood how to insert an element in the queue but how to access the topmost element?

We can do that easily by using the peek function. Let us understand it more by the following piece of code.

peek()

The peek() method simply returns the topmost element present in the priority queue.

 

class PriorityQueueDemo {
  
    // Main Method.
    public static void main(String args[])
    {
        // Creating an empty priority queue.
        PriorityQueue<Integer> pQ = new PriorityQueue<Integer>();
 
        // Adding items to the pQueue using add() method.
        pQ.add(88);
        pQ.add(98);
 
        // Printing the top element of PriorityQueue.
        System.out.println(pQ.peek());


 
    }
}

 

Output

98

Time Complexity

O(1)

 

What if I have to delete the topmost element?

To do that we can simply use the poll() function. Here is an example.

poll()

The poll() method deletes the topmost element of the priority queue.

public class PriorityQueueDemo {
 
    public static void main(String args[])
    {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
 
        pq.add(1);
        pq.add(2);
        pq.add(3);

        // Printing top element before deletion.
        System.out.println(pq.peek());

        
        // Using poll() to delete the topmost element.
        pq.poll();


        // Printing top element after deletion.             
        System.out.println(pq.peek());
    }
}

 

Output

3 2

 

Time Complexity

O(1)

 

Other Methods

By now, you have understood the basic methods of the priority queue using java. Now let’s look at some other important methods that are provided in java.

 

• clear()

It is used to remove all the elements from the priority queue.   

        PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
  
        // Adding elements to our priority queue.
        queue.add(15);        
        queue.add(10);
        
          
        // Displaying priority queue before clear().
        System.out.println(pq);
  
        // Using clear() to remove all elements          

        queue.clear();
  
        // After clear() the status of the priority queue.
        System.out.println(pq);

  

Output

[15,12] []

 

Time Complexity

O(N), where ‘N’ is the number of elements in the priority queue.

 

• contains()

It is used to check if an element is present in the queue or not. If yes, it returns true, else returns false.

       PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
  
        // Adding elements to our priority queue.
        queue.add(15);        
        queue.add(10);
        
          
        // Displaying priority queue before clear().
        System.out.println(pq.contains(15));

        // Calling clear function
        pq.clear();
  
        // After clear() the status of the priority queue.
        System.out.println(pq.contains(2));

 

Output

 

true false

 

Time Complexity

O(1)

 

• iterator()

It returns an iterator to iterate over the elements in the priority queue.

       PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
  
        // Adding elements to our priority queue.
        queue.add(15);        
        queue.add(10);
        
        // Assigning an iterator to the variable 'it'.
        Iterator it=pq.iterator();
        
        // Iterating over priority queue using iterator
        while (it.hasNext()) {
            System.out.println(it.next());
        }

 

 

Output

15 10

 

• remove(obj)

It removes the obj from the priority queue if present. If more than one obj is present, it will remove only one of them.

        PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
  
        // Adding elements to our priority queue.
        queue.add(15);        
        queue.add(10);

        queue.add(11);
        
          
        // Displaying priority queue before using remove().
        System.out.println(pq);

        // Calling clear function
        pq.remove(15);
  
        // After clear() the status of the priority queue.
        System.out.println(pq);

 

Output

[15,11,10] [11,10]

 

Time Complexity

O(1)

If the element is not present in the queue then the compiler throws an exception.

 

• toArray()
• It returns us an array containing all of the elements in the queue.

      PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
  
        // Adding elements to our priority queue.
        queue.add(15);        
        queue.add(10);

        queue.add(12);
        
          
        // Displaying priority queue before clear().
        System.out.println(pq);

 

        // Elements of the queue will be stored in array ‘arr’.
        Object[] arr = queue.toArray();
  
        // Printing the array
        for (int i = 0; i < arr.length; i++)
            System.out.println(arr[i]);

Output

[15,12,10]

 

 

Read about Application of Queue in Data Structure here.

Frequently Asked Questions

Which data structure does a priority queue utilize?

The priority queue makes use of a heap data structure. Depending upon the requirements, it can be either a min-heap or a max-heap.

What is the insertion complexity for an element in the priority queue?

The insertion complexity for an element in the priority queue is O(logN) where N is the size of the priority queue.

Conclusion

Now that you have mastered the basics of priority queue using Java and saw how we could use its inbuilt methods to perform different functions. 

Some Important Practice Problems on Priority Queue

1. Rearrange the Array
2. Sort A “K” Sorted Doubly Linked List 
3. Merge K Sorted Arrays
4. Matrix Median
5. Implement a Priority Queue

Recommended Readings:

• Priority Queue of Pairs in C++ With Ordering
• Applications of Priority Queue
• Priority Queue Using A Linked List
• Heap and Priority Queue
• Priority Queue Using Array in C++
• Doubly Linked List

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!