Difference Betwixt Priorityqueue As Well As Treeset Inward Java?

The PriorityQueue together with TreeSet collection classes has a lot of similarities e.g. both render O(log(N)) fourth dimension complexity for adding, removing, together with searching elements, both are non-synchronized together with y'all tin forcefulness out acquire chemical component from both PriorityQueue together with TreeSet inwards sorted order, but at that spot is primal divergence betwixt them, TreeSet is a Set together with doesn't allow a duplicate element, acre PriorityQueue is a queue together with doesn't receive got such restriction. It tin forcefulness out incorporate multiple elements amongst equal values together with inwards that illustration caput of the queue volition live on arbitrarily chosen from them. Another key divergence betwixt TreeSet together with PriorityQueue is iteration order, though y'all tin forcefulness out access elements from the caput inwards a sorted gild e.g. caput ever give y'all lowest or highest priority chemical component depending upon your Comparable or Comparator implementation but iterator returned yesteryear PriorityQueue doesn't render whatever ordering guarantee.

Only guarantee PriorityQueue gives that caput volition ever live on smallest or largest element. On the other hand, TreeSet keeps all elements inwards sorted gild together with iterator returned yesteryear TreeSet volition allow y'all to access all elements inwards that sorted order.

This is i of the oftentimes asked Collection interview questions together with what makes it interesting is the subtle divergence betwixt a lot of similarities betwixt PriorityQueue together with TreeSet.  You tin forcefulness out utilisation i inwards house of around other inwards around scenarios but non inwards all scenarios together with that's what Interviewer is looking for when he inquire this inquiry to y'all on Interview.

Similarity betwixt PriorityQueue together with TreeSet

Before looking at the divergence betwixt PriorityQueue together with TreeSet, let's get-go empathise the similarities betwixt them. This volition assistance y'all to think of scenarios where y'all tin forcefulness out utilisation a PriorityQueue inwards house of TreeSet or vice-versa. 

ThreadSafety
First similarities betwixt PriorityQueue together with TreeSet is that both are non thread-safe, which agency y'all cannot portion them betwixt multiple threads. If multiple threads are required to alter the TreeSet at the same time, together with so y'all must synchronize their access externally.

Ordering
The 3rd similarity betwixt PriorityQueue together with TreeSet is that both tin forcefulness out live on used to access elements inwards a exceptional order. TreeSet is a SortedSet, therefore it ever keeps the elements inwards the gild defined yesteryear their Comparator or natural gild if at that spot is no Comparator defined, acre PriorityQueue volition ever brand certain that caput contains the lowest or highest value depending upon the gild imposed yesteryear Comparator or Comparable.

Eligibility 
When I nation eligibility, which agency which objects tin forcefulness out live on stored inwards PrioritySet together with TreeSet? Is at that spot whatever restriction or all objects are allowed? Well, at that spot is, y'all tin forcefulness out exclusively shop objects which implement Comparable or Comparator inwards both PriorityQueue together with TreeSet because the collection classes are responsible for keeping their commitment i.e. PriorityQueue must adjust afterward every insertion or deletion to proceed the lowest or highest chemical component inwards caput position. Similarly, TreeSet must re-arrange elements so that they rest the sorted gild specified yesteryear Comparator or natural gild imposed yesteryear Comparable.


Performance
This is i indicate where y'all volition encounter both similarity together with divergence betwixt PriorityQueue together with TreeSet inwards Java i.e. both provides O(log(N)) complexity for adding, removing together with searching elements, but when y'all desire to take the highest or lowest priority chemical component together with so PriorityQueue gives O(1) performance because it ever proceed the chemical component inwards head, much similar a heap information construction i.e. minimum heap where source is ever the minimum value.  If y'all are non familiar amongst heap information structure, I advise y'all reading a skilful mass on information construction e.g. Algorithms 4th Edition yesteryear Robert Sedgewick.

Difference betwixt PriorityQueue together with TreeSet

Now, that y'all know together with empathise similarities betwixt TreeSet together with PrioritySet, let's encounter how dissimilar they are? together with why y'all cannot utilisation PrioritySet inwards house of TreeSet inwards Java?


Underlying Data Structure
This get-go together with firstly divergence is underlying information structure. PriorityQueue is a Queue together with that's why it provides the functionality of FIFO information structure, acre TreeSet is a Set together with doesn't render the Queue API.


Duplicate Elements
The 2nd divergence betwixt them tin forcefulness out live on derived from the get-go divergence i.e. properties of their underlying information structure. Since TreeSet is a Set it doesn't allow duplicate elements but PriorityQueue may incorporate duplicates. In the illustration of ties, the caput of the priority queue is chosen arbitrarily.



Performance
The 3rd divergence betwixt TreeSet together with PrirityQueue comes from their relative performance. The PriorityQueue provides largest or smallest chemical component inwards O(1) time, which is non possible yesteryear TreeSet. Since TreeSet is backed yesteryear a red dark tree, the search performance volition accept O(logN) time. This is why if y'all are developing an application where priority matters e.g. a chore scheduling algorithm where y'all ever desire to execute the chore amongst the highest priority, y'all should utilisation PriorityQueue information structure.


Availability
The fifth together with final divergence betwixt PriorityQueue together with TreeSet degree are that old was added inwards JDK 1.5 acre TreeSet was available from JDK 1.4 itself. This is non a really pregnant divergence inwards the historic catamenia of Java 8, but if y'all are working amongst legacy systems nonetheless running on Java 1.5, a indicate worth remembering.


Ordering
The 4th difference, which is to a greater extent than subtle than y'all think because inwards similarities I receive got told that both are responsible for keeping around ordering. The key indicate is that inwards TreeSet all elements rest inwards the sorted order, acre inwards priority queue apart from root, which is guaranteed to live on smallest or largest depending upon Comparing logic, residue of chemical component may or may non follow whatever ordering.

This agency if y'all shop same elements inwards the TreeSet together with PriorityQueue together with iterate over them, together with so their gild volition live on different. TreeSet volition impress them inwards sorted gild but PriorityQueue volition non until y'all are ever getting the chemical component from the head.  You tin forcefulness out read a skilful substance Java mass e.g. Java: The Complete Reference, Ninth Edition to larn to a greater extent than most PriorityQueue implementation inwards Java.

Using PriorityQueue together with TreeSet inwards Java Program

Now, let's around code to highlight the divergence betwixt PriorityQueue together with TreeSet inwards Java. If y'all scream upward the most subtle divergence I get upward inwards the previous paragraph was that TreeSet keeps all elements inwards the sorted order, acre PriorityQueue exclusively keeps the source or caput into order. I hateful the lowest chemical component volition ever live on at source inwards PriorityQueue. If y'all utilisation poll() which consumes the caput together with removes it, y'all volition ever retrieve the elements inwards increasing gild from PriorityQueue, equally shown inwards next 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 divergence betwixt PriorityQueue  * together with 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 together with PriorityQueue       setOfNumbers.add(202);       setOfNumbers.add(102);       setOfNumbers.add(503);       setOfNumbers.add(33);              queueOfNumbers.add(202);       queueOfNumbers.add(102);       queueOfNumbers.add(503);       queueOfNumbers.add(33);              // Iterating over TreeSet       System.out.println("Iterating over TreeSet inwards Java");       Iterator itr = setOfNumbers.iterator();       while(itr.hasNext()){         System.out.println(itr.next());       }              // Iterating over PriorityQueue       System.out.println("Iterating over PriorityQueue inwards Java");       itr = queueOfNumbers.iterator();       while(itr.hasNext()){         System.out.println(itr.next());       }              // Consuming numbers using from caput inwards PriorityQueue       System.out.println("polling a PriorityQueue inwards Java");       while(!queueOfNumbers.isEmpty()){         System.out.println(queueOfNumbers.poll());       }   }        }  Output: Iterating over TreeSet inwards Java 33 102 202 503 Iterating over PriorityQueue inwards Java 33 102 503 202 polling a PriorityQueue inwards Java 33 102 202 503 

You tin forcefulness out encounter that the gild is dissimilar from the Iterator returned yesteryear PriorityQueue together with HeadSet (highlighted yesteryear red) but when y'all utilisation the poll() method to swallow all elements inwards PriorityQueue, y'all receive got got them inwards the same gild they were acquaint inwards TreeSet i.e. lowest to highest. This proves the indicate that TreeSet keeps all elements inwards sorted order acre PriorityQueue exclusively attention most the source or caput position. This sort of details are really of import from Java certification perspective equally well, y'all volition notice a lot of questions based upon such subtle details inwards mock exams also equally on the existent exam.

Summary

Finally, hither is the summary of all the differences betwixt TreeSet together with PriorityQueue inwards Java on the dainty tabular format for slow reference:

That's all most the difference betwixt TreeSet together with PrirorityQueue inwards Java. Though both provides around sort of sorting capability at that spot is a huge divergence betwixt the direct of these ii collection classes. The get-go together with most of import divergence is i is Set together with other is Queue, which agency i doesn't allow duplicate acre other is FIFO information construction without whatever restriction on duplication.  If y'all desire to larn to a greater extent than most advanced information construction together with collection classes inwards Java, I advise to read a skilful mass substance Java e.g. Core Java For the Impatient yesteryear Cay. S. Horstmann.

Further Learning
Java In-Depth: Become a Complete Java Engineer
answer)

Difference betwixt Hashtable together with HashMap inwards Java? (answer)

Difference betwixt HashMap together with LinkedHashMap inwards Java? (answer)

Difference betwixt ConcurrentHashMap together with HashMap inwards Java? (answer)

Difference betwixt ArrayList together with Vector inwards Java? (answer)

Difference betwixt ArrayList together with LinkedList inwards Java? (answer)

Difference betwixt TreeMap, HashMap, together with LinkedHashMap inwards Java? (answer)

Difference betwixt fail-fast together with fail-safe Iterator inwards Java? (answer)

Difference betwixt HashMap, Hashtable, together with ConcurrentHashMap inwards Java? (answer)

Difference betwixt an Array together with ArrayList inwards Java? (answer)

Difference betwixt synchronized ArrayList together with CopyOnWriteArrayList inwards Java? (answer)

Thanks for reading this article so far, if y'all similar this article together with so delight portion amongst your friends together with colleagues. If y'all receive got whatever questions or feedback together with so delight drib a comment.

Sumber https://javarevisited.blogspot.com/

Share this post