For Software Engineers, preparing for a tech interview means a lot of practice! Not only must you practice a diverse set of problems, but you also need to ensure that you cover a wide variety of topics. 

In this article, we’re going to cover a topic related to the collection framework in Java, which will, in turn, help you crack several complex problems based on PriorityQueue in Java.

We will be covering: 

• Why Do We Need Queues?
• What is PriorityQueue in Java?
• How PriorityQueue Works in Java?
• Java PriorityQueue Class
• Java PriorityQueue Features
• PriorityQueue Methods
• Custom ordering in PriorityQueue.
• FAQs on PriorityQueue in Java

Why Do We Need PriorityQueue?

Queue follows the FIFO(First In First Out) principle. The person who came first will get out of the queue first. 

Consider a scenario when different tourists are visiting a particular place, say Taj mahal. Some of them are VVIP, VIP, etc. So, if a VVIP person comes into the queue, we need to take him to the front of the queue. 

Here, each person has a priority, and to maintain such kinds of queues, we need a data structure that can process nodes according to their priorities. For this purpose, we can use a data structure known as “PriorityQueue”

What is PriorityQueue in Java?

Based on the concept of priority heap, PriorityQueue is a class member of the Java collection framework. The processing of the elements in PriorityQueue happens based on the priority of elements. 

Example:

Suppose we have an array of strings consisting of lowercase English letters. We need to reorder this string such that the conditions below hold:

• The elements having a larger number of a’s in the string will come first.
• If two strings have the same number of a’s, then they will come in sorted order.

Let the given strings be S = { “aaa”, “aaz”,”aab”}

We will be inserting each string in a PriorityQueue.

Our priority queue is initially empty, PQ = { }

Step 1:

S = { “aaa”, “aaz”, ”aab”} and PQ = { }

Here “aaa” has the maximum number of a’s thereby has maximum priority, so it will come in front of the queue.

Now S = { “aaz”, ”aab” } and PQ = { “aaa” }

Step 2:

S = { “aaz”,”aab” } and PQ = { “aaa” }

Here priority of “aab” > “aaz” since both have same number of a’s, but “aab” is lexicographically smaller than “aaz”.

Now S = { “aaz” } and PQ = { “aaa”, ”aab” }

Step 3:

S = { “aaz” } and PQ = { “aaa”, ”aab” }

Here only “aaz” remains in the array so push it in the queue.

Finally, PQ = { “aaa”, ”aab”, “aaz” }

How PriorityQueue works in Java?

PriorityQueue works internally based on the binary heap. The ordering of the elements of the priority queue occurs according to natural ordering or custom order based upon the implementation. We use comparators to use custom orders in PriorityQueue. 

Internally PriorityQueue maintains a binary heap such that the top elements of the queue become the root node of the queue. Both insertion and deletion operations in the binary heap take O(logN) time. Also, the time taken for constructing a binary heap is O(N). So the time taken for the construction of PriorityQueue will be O(N). Here, “N” is the total number of elements in the queue.

Java PriorityQueue class

Syntax:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

where E is the type of elements contained in the queue.

This class implements the following interfaces:

• Serializable
• Iterable<E>
• Collection<E>
• Queue<E>

Java PriorityQueue features

It supports the following features:

• It supports insertion, removal, and access of the priority element in log(N) time,
• It supports the only similar types of objects that are comparable.
• It does not support NULL elements.
• PriorityQueues are unbounded queues, and their capacity can grow dynamically.
• If two elements have the same priority, then the element which will come next will be chosen arbitrarily between the two.
• PriorityQueues are not thread-safe.

Java PriorityQueue Methods

Let us now look at some of the methods associated with PriorityQueue in Java.

Constructors:

PriorityQueue(): 

It creates a priority queue with default capacity(11) and orders elements according to natural ordering.

Syntax:

• PriorityQueue<E> PQ = new PriorityQueue<E>();
• where E is the type of elements contained in the queue.

PriorityQueue(int capacity): 

It creates a priority queue with the given default capacity and orders elements according to their natural ordering.

Syntax:

• PriorityQueue<E> PQ = new PriorityQueue<E>(int capacity); 
• where E is the type of elements contained in the queue.

PriorityQueue(Collection<E> c): 

It creates a PriorityQueue that contains elements in a specified collection.

Syntax:

• PriorityQueue<E> PQ = new PriorityQueue<E>(Collection<E> c);
• where E is the type of elements contained in the queue.

PriorityQueue(int capacity, Comparator<E> comparator): 

It creates a PriorityQueue with capacity and order elements according to the specified comparator.

Syntax:

• PriorityQueue<E> PQ = new PriorityQueue<E>(int capacity, Comparator<E> comparator);
• where E is the type of elements contained in the queue.

PriorityQueue(PriorityQueue<E> c): 

It creates a PriorityQueue containing elements in the specified priority queue.

Syntax:

• PriorityQueue<E> PQ = new PriorityQueue<E>(PriorityQueue<E> c);
• where E is the type of elements contained in the queue.

PriorityQueue(SortedSet<E> c): 

It creates a PriorityQueue containing elements in the specified sorted set.

Syntax:

• PriorityQueue<E> PQ = new PriorityQueue<E>(SortedSet<E> c);
• where E is the type of elements contained in the queue.

Operations on PriorityQueue

Add an element:

After adding an element, the priorityQueue reorders itself such that the element having the highest priority will come first.

Syntax:

• PQ.add(E);
• where E is the type of elements contained in the queue.

Program:

import java.util.*;

import java.io.*;

public class priorityQueue {

    public static void main(String args[]) {

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

        pq.add(4);

        pq.add(2);

        pq.add(1);

        pq.add(10);

        pq.add(7);

        System.out.println(pq);

    }

}

Output:

[1, 4, 2, 10, 7]

Here elements are not in sorted order, and the top element of PriorityQueue is the minimum element.

Removing elements:

We can use remove() or poll() for this purpose.

remove() Syntax:

• PQ.remove(E)
• where E is the type of elements contained in the queue.
• It removes the first occurrence of E from PriorityQueue.

poll() Syntax:

• PQ.poll
• It removes the head/top element of PriorityQueue.

Program:

import java.util.*;

import java.io.*;

public class priorityQueue {

    public static void main(String args[]) {

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

        pq.add(4);

        pq.add(2);

        pq.add(1);

        pq.add(10);

        pq.add(7);

        System.out.println("Priority Queue :" + pq);

        pq.remove(10);

        System.out.println("Priority Queue After remove(10):" + pq);

        pq.poll();

        System.out.println("Priority Queue After poll():" + pq);

    }

}

Output:

Priority Queue :[1, 4, 2, 10, 7]

Priority Queue After remove(10):[1, 4, 2, 7]

Priority Queue After poll():[2, 4, 7]

Accessing the elements:

We can only access the head of PriorityQueue. For this, we can use the peek() function.

Syntax:

• PQ.peek()
• It returns the head of the PriorityQueue.

Program:

import java.util.*;

import java.io.*;

public class priorityQueue {

    public static void main(String args[]) {

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

        pq.add(4);

        pq.add(2);

        pq.add(1);

        pq.add(10);

        pq.add(7);

        System.out.println("Head element :" + pq.peek());

    }

}

Iterating PriorityQueue:

PriorityQueue has an inbuilt iterator that we can use to traverse the priorityQueue.

Program:

import java.util.*;

import java.io.*;

public class priorityQueue {

    public static void main(String args[]) {

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

        pq.add(4);

        pq.add(2);

        pq.add(1);

        pq.add(10);

        pq.add(7);

        Iterator iterator = pq.iterator();

        while (iterator.hasNext()) {

            System.out.print(iterator.next() + " ");

        }

    }

}

Some More Useful Methods

Following are four more handy priority queue methods:

• clear(): It removes all elements from the priority queue.
• offer(E): It adds an element E into priority queue
• contains(E): It returns true if PriorityQueue contains E; else, it returns false.
• isEmpty(): It returns true if PriorityQueue is empty 

Let us now see how these methods work with the help of an example:

Program:

import java.util.*;

import java.io.*;

public class priorityQueue {

    public static void main(String args[]) {

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

        pq.offer(4);

        pq.offer(2);

        pq.offer(1);

        pq.offer(10);

        pq.offer(7);

        System.out.println("pq.contains(4):" + pq.contains(4));

        pq.clear();

        System.out.println("pq after clear():" + pq);

    }

}

Output:

pq.contains(4):true

pq after clear():[]

Custom Ordering in PriorityQueue

The default ordering of PriorityQueue is in ascending order. We can change this to a custom order by using comparator(). comparator() takes 2 arguments (the elements which we need to compare) and returns:

• 0: When both elements have the same priority.
• 1: When the second element should come first.
• -1: When the first element should come first.

Suppose one of the FAANG companies conducted a drive for recruitment and shortlisted some candidates for the interview. For this, they want to interview a candidate who has solved the maximum number of problems. 

Here, we have a list where the element of the list contains [candidateName, Number of problems solved by the candidate], and we want to do this such that the person who solved more problems will come first.

So, we can solve this problem by building a custom comparator in PriorityQueue.

Program:

import java.util.*;

import java.io.*;

public class priorityQueue {

    public static void main(String args[]) {

        PriorityQueue<candidates> pq = new PriorityQueue<candidates>(new customComparator());

        candidates candidate1 = new candidates("candidate1", 450);

        candidates candidate2 = new candidates("candidate2", 150);

        candidates candidate3 = new candidates("candidate3", 50);

        candidates candidate4 = new candidates("candidate4", 200);

        pq.add(candidate1);

        pq.add(candidate2);

        pq.add(candidate3);

        pq.add(candidate4);

        while (!pq.isEmpty()) {

            System.out.println(pq.peek().getName() + " has solved " + pq.poll().problemsSolved + " problems.");

        }

    }

}

// Overriding compare()method of Comparator

// for descending order of number of problems solved

class customComparator implements Comparator<candidates> {

    @Override

    public int compare(candidates a, candidates b) {

        if (a.problemsSolved < b.problemsSolved)

            return 1;

        else if (a.problemsSolved > b.problemsSolved)

            return -1;

        return 0;

    }

}

// Candidate class

class candidates {

    public String name;

    public int problemsSolved;

    public candidates(String name, int problemsSolved) {

        this.name = name;

        this.problemsSolved = problemsSolved;

    }

    public String getName() {

        return name;

    }

}

Output:

candidate1 has solved 450 problems.

candidate4 has solved 200 problems.

candidate2 has solved 150 problems.

candidate3 has solved 50 problems.

FAANG Interview Questions on Java

Question: What are the applications of PriorityQueue in Java? What happens if we try to remove an element that doesn’t exceed in PriorityQueue?

We use PriorityQueue in Dijkstra and Prims Algorithms. The remove() function will return false in that case, and no element will get removed from PriorityQueue. We also use it in Huffman Codes.

Question: What happens if we try to poll an element from an empty PriorityQueue?

It returns false, and no element will get removed from PriorityQueue.

Are You Ready to Nail Your Next Coding Interview?

Whether you’re a Coding Engineer gunning for Software Developer or Software Engineer roles, or you’re targeting management positions at top companies, IK offers courses specifically designed for your needs to help you with your technical interview preparation!

If you’re looking for guidance and help with getting started, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of Software Engineers to crack the most challenging coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

————

Article contributed by Pankaj Sharma