• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

PriorityQueue v/s TreeSet

 
Ranch Hand
Posts: 441
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I feel that PriorityQueue and TreeSet works similarly except one that TreeSet doesn't allow duplicates. Is there any other difference in functionality which can't be achieved using PriorityQueue & TreeSet interchangeably.
 
Saloon Keeper
Posts: 15510
363
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
PriorityQueue is implemented using binary min heaps, which are optimized for fast retrieval/removal of the smallest (highest priority) element. TreeSet is implemented using red-black trees, and can be quickly searched for a random element, but can't retrieve and remove the smallest element as fast.

TreeSet is completely sorted. If you iterate over one, you will get all elements sorted from smallest to greatest. PriorityQueue is only partially sorted. When you iterate over one, the order may appear random, and the only guarantee is that the first element will be the smallest.

TreeSet has a whole bunch of useful methods that it can perform because it keeps its elements in sorted order. Check out the NavigableSet interface to see which.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Note that you can get all elements of a PriorityQueue in sorted order, but this is a destructive operation. You can only do it once and then the queue will contain no more elements:
 
Vaibhav Gargs
Ranch Hand
Posts: 441
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you Stephan for sharing detailed analysis.
 
reply
    Bookmark Topic Watch Topic
  • New Topic