Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Declaration of Priority Queue using Java
3.
Frequently used PriorityQueue Methods
3.1.
add()
3.2.
peek()
3.3.
poll()
3.4.
Other Methods
4.
 
5.
Frequently Asked Questions
5.1.
Which data structure does a priority queue utilize?
5.2.
What is the insertion complexity for an element in the priority queue?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Priority Queue using Java

Author Saksham Gupta
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Heap and Priority Queue

Introduction

While stacks have a last-in-first-out (LIFO mechanism) and queues have a first-in-first-out mechanism (FIFO), priority queues are somewhat different. Just by the name itself, a priority queue is just a queue — with the added extension of associating a “priority” to each item in the queue. Just like queues, priority queues also have a FIFO mechanism. But what does “priority” mean in this case? What does it mean to assign a “priority” to an item in the queue? 

 

Generally, the element’s value is considered for assigning the priority, i.e., its magnitude. For example, the element whose magnitude is highest is considered to be the element with the highest priority. However, in other cases, we can also mark an element with the lowest value as the element with the highest priority. Priorities can also be set by our needs.

priority queue

 

Thus we can classify them into two categories.

  1. Min Priority Queue: Minimum element has the highest priority.
  2. Max Priority Queue: Maximum element has the highest priority.

 

Now, this sounds very interesting but you must be thinking about how to implement it, the answer is a heap data structure. Heaps? What are they?

heap is a data structure based on trees where the root of the tree contains the element whose priority is the highest or the lowest. A heap is a complete binary tree, Another new word? Well, in a complete binary tree every node has two child nodes except the leaf nodes. This means all the leaf nodes should be at the same level and all other internal nodes should contain two child nodes each.

Complete Binary Tree

                                                

In the first image, all levels are filled and have two children except the leaf nodes, whereas if we look at the second image, some nodes don't have two children (node with value 3).

Also Read, Prefix Sum Array

Declaration of Priority Queue using Java

Now let’s talk about the declaration of priority queue using Java. We can use different constructors to declare our priority queue.

 

1. PriorityQueue(): Creates a PriorityQueue with the initial default capacity (11) that orders its elements according to their natural ordering.

PriorityQueue<E> pq = new PriorityQueue<E>();

 

2. PriorityQueue(Collection<E> c): Creates a PriorityQueue containing the elements in the specified collection.

PriorityQueue<E> pq = new PriorityQueue<E>(Collection<E> c);

 

3. PriorityQueue(int initialCapacity): Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.

 

PriorityQueue<E> pq = new PriorityQueue<E>(int initialCapacity);

4. PriorityQueue(int initialCapacity, Comparator<E> comparator): Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.

PriorityQueue<E> pq = new PriorityQueue(int initialCapacity, Comparator<E> comparator);

 

5. PriorityQueue(PriorityQueue<E> c): Creates a PriorityQueue containing the elements in the specified priority queue.

PriorityQueue<E> pq = new PriorityQueue(PriorityQueue<E> c);

 

6. PriorityQueue(SortedSet<E> c): Creates a PriorityQueue containing the elements in the specified sorted set.

PriorityQueue<E> pq = new PriorityQueue<E>(SortedSet<E> c);

 

Here ‘E’ refers to the type of element(Integer, String, etc.).

 

Let's now see some frequently used methods that are used to perform operations on the Priority Queue.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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:


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!

Next article
Double Ended Priority Queue
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass