Priority Queue using Java

Saksham Gupta
Last Updated: May 13, 2022

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.

                                                                                                   Source: AfterAcademy

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.

 

                                               

                                                                                                     Source: TechieDelight

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).

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.

Frequently used PriorityQueue Methods

 

add()

The add() method as the name suggests is used to add a 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]

 

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

 

Key Takeaways

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. It’s time to move ahead to CodeStudio and practice some famous interview problems on the priority queue. CodeStudio offers interesting interview experiences and blogs like this one. Till then, keep learning, and Happy Coding!

By:- Saksham Gupta

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think