Thursday, 27 July 2017

Difference between PriorityQueue and TreeSet in Java?

The PriorityQueue and TreeSet collection classes has a lot of similarities e.g. both provide O(log(N)) time complexity for adding, removing, and searching elements, both are non-synchronized and you can get element from both PriorityQueue and TreeSet in sorted order, but there is fundamental difference between them, TreeSet is a Set and doesn't allow a duplicate element, while PriorityQueue is a queue and doesn't have such restriction. It can contain multiple elements with equal values and in that case head of the queue will be arbitrarily chosen from them. Another key difference between TreeSet and PriorityQueue is iteration order, though you can access elements from the head in a sorted order e.g. head always give you lowest or highest priority element depending upon your Comparable or Comparator implementation but iterator returned by PriorityQueue doesn't provide any ordering guarantee.

Only guarantee PriorityQueue gives that head will always be smallest or largest element. On the other hand, TreeSet keeps all elements in sorted order and iterator returned by TreeSet will allow you to access all elements in that sorted order.

This is one of the frequently asked Collection interview questions and what makes it interesting is the subtle difference between a lot of similarities between PriorityQueue and TreeSet.  You can use one in place of another in some scenarios but not in all scenarios and that's what Interviewer is looking for when he ask this question to you on Interview.

Similarity between PriorityQueue and TreeSet

Before looking at the difference between PriorityQueue and TreeSet, let's first understand the similarities between them. This will help you to think of scenarios where you can use a PriorityQueue in place of TreeSet or vice-versa.


First similarities between PriorityQueue and TreeSet is that both are not thread-safe, which means you cannot share them between multiple threads. If multiple threads are required to modify the TreeSet at the same time, then you must synchronize their access externally.


The third similarity between PriorityQueue and TreeSet is that both can be used to access elements in a particular order. TreeSet is a SortedSet, hence it always keeps the elements in the order defined by their Comparator or natural order if there is no Comparator defined, while PriorityQueue will always make sure that head contains the lowest or highest value depending upon the order imposed by Comparator or Comparable.


When I say eligibility, which means which objects can be stored in PrioritySet and TreeSet? Is there any restriction or all objects are allowed? Well, there is, you can only store objects which implement Comparable or Comparator in both PriorityQueue and TreeSet because the collection classes are responsible for keeping their commitment i.e. PriorityQueue must adjust after every insertion or deletion to keep the lowest or highest element in head position. Similarly, TreeSet must re-arrange elements so that they remain the sorted order specified by Comparator or natural order imposed by Comparable.


This is one point where you will see both similarity and difference between PriorityQueue and TreeSet in Java i.e. both provides O(log(N)) complexity for adding, removing and searching elements, but when you want to remove the highest or lowest priority element then PriorityQueue gives O(1) performance because it always keep the element in head, much like a heap data structure i.e. minimum heap where root is always the minimum value.  If you are not familiar with heap data structure, I suggest you reading a good book on data structure e.g. Algorithms 4th Edition by Robert Sedgewick.

Difference between PriorityQueue and TreeSet

Now, that you know and understand similarities between TreeSet and PrioritySet, let's see how different they are? and why you cannot use PrioritySet in place of TreeSet in Java?

Underlying Data Structure

This first and foremost difference is underlying data structure. PriorityQueue is a Queue and that's why it provides the functionality of FIFO data structure, while TreeSet is a Set and doesn't provide the Queue API.

Duplicate Elements

The second difference between them can be derived from the first difference i.e. properties of their underlying data structure. Since TreeSet is a Set it doesn't allow duplicate elements but PriorityQueue may contain duplicates. In the case of ties, the head of the priority queue is chosen arbitrarily.


The third difference between TreeSet and PrirityQueue comes from their relative performance. The PriorityQueue provides largest or smallest element in O(1) time, which is not possible by TreeSet. Since TreeSet is backed by a red black tree, the search operation will take O(logN) time. This is why if you are developing an application where priority matters e.g. a job scheduling algorithm where you always want to execute the job with the highest priority, you should use PriorityQueue data structure.


The 5th and last difference between PriorityQueue and TreeSet class are that former was added in JDK 1.5 while TreeSet was available from JDK 1.4 itself. This is not a very significant difference in the age of Java 8, but if you are working with legacy systems still running on Java 1.5, a point worth remembering.


The fourth difference, which is more subtle than you think because in similarities I have told that both are responsible for keeping some ordering. The key point is that in TreeSet all elements remain in the sorted order, while in priority queue apart from root, which is guaranteed to be smallest or largest depending upon Comparing logic, rest of element may or may not follow any ordering.

This means if you store same elements in the TreeSet and PriorityQueue and iterate over them, then their order will be different. TreeSet will print them in sorted order but PriorityQueue will not until you are always getting the element from the head.  You can read a good core Java book e.g. Java: The Complete Reference, Ninth Edition to learn more about PriorityQueue implementation in Java.

Using PriorityQueue and TreeSet in Java Program

Now, let's some code to highlight the difference between PriorityQueue and TreeSet in Java. If you remember the most subtle difference I mention in the previous paragraph was that TreeSet keeps all elements in the sorted order, while PriorityQueue only keeps the root or head into order. I mean the lowest element will always be at root in PriorityQueue. If you use poll() which consumes the head and removes it, you will always retrieve the elements in increasing order from PriorityQueue, as shown in following Java program.

import java.util.Collections;
import java.util.Date;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;

 * Java Program to demonstrate difference between PriorityQueue
 * and TreeSet.
 * @author WINDOWS 8
public class App {

  public static void main(String args[]) {

      Set setOfNumbers = new TreeSet<>();
      Queue queueOfNumbers = new PriorityQueue<>();
      // inserting elements into TreeSet and PriorityQueue
      // Iterating over TreeSet
      System.out.println("Iterating over TreeSet in Java");
      Iterator itr = setOfNumbers.iterator();
      // Iterating over PriorityQueue
      System.out.println("Iterating over PriorityQueue in Java");
      itr = queueOfNumbers.iterator();
      // Consuming numbers using from head in PriorityQueue
      System.out.println("polling a PriorityQueue in Java");



Iterating over TreeSet in Java
Iterating over PriorityQueue in Java
polling a PriorityQueue in Java

You can see that the order is different from the Iterator returned by PriorityQueue and HeadSet (highlighted by red) but when you use the poll() method to consume all elements in PriorityQueue, you have got them in the same order they were present in TreeSet i.e. lowest to highest. This proves the point that TreeSet keeps all elements in sorted order while PriorityQueue only care about the root or head position. This kind of details are very important from Java certification perspective as well, you will find a lot of questions based upon such subtle details in mock exams as well as on the real exam.

PriorityQueue and TreeSet in Java

Related Posts