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:
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â€
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.
Suppose we have an array of strings consisting of lowercase English letters. We need to reorder this string such that the conditions below hold:
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†}
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.
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:
It supports the following features:
Let us now look at some of the methods associated with PriorityQueue in Java.
PriorityQueue():
It creates a priority queue with default capacity(11) and orders elements according to natural ordering.
Syntax:
PriorityQueue(int capacity):
It creates a priority queue with the given default capacity and orders elements according to their natural ordering.
Syntax:
PriorityQueue(Collection<E> c):
It creates a PriorityQueue that contains elements in a specified collection.
Syntax:
PriorityQueue(int capacity, Comparator<E> comparator):
It creates a PriorityQueue with capacity and order elements according to the specified comparator.
Syntax:
PriorityQueue(PriorityQueue<E> c):
It creates a PriorityQueue containing elements in the specified priority queue.
Syntax:
PriorityQueue(SortedSet<E> c):
It creates a PriorityQueue containing elements in the specified sorted set.
Syntax:
Add an element:
After adding an element, the priorityQueue reorders itself such that the element having the highest priority will come first.
Syntax:
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:
poll() Syntax:
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:
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() + ” “);
}
}
}
Following are four more handy priority queue methods:
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():[]
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:
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.
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.
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!
————
Article contributed by Pankaj Sharma
Time Zone:
Get your enrollment process started by registering for a Pre-enrollment Webinar with one of our Founders.
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
Just drop your name and email so we can send your Power Patterns PDF straight to your inbox. No Spam!
By sharing your contact details, you agree to our privacy policy.
Time Zone: Asia/Dhaka
We’ve sent the Power Patterns PDF to your inbox — it should arrive in the next 30 seconds.
📩 Can’t find it? Check your promotions or spam folder — and mark us as safe so you don’t miss future insights.
We’re hosting a private session where FAANG insiders walk through how they actually use these Power Patterns to crack interviews — and what sets top performers apart.
🎯 If you liked the PDF, you’ll love what we’re sharing next.
Time Zone:
