Search

Saturday, July 4, 2015

How to use PriorityQueue in Java? An Example

PriorityQueue is another data structure from Java Collection framework, added in Java SE 5. This class implements Queue interface and provides a sorted element from head of the queue. Though it provides sorting, its little different with other Sorted collections e.g. TreeSet or TreeMap, which also allows you to iterate over all elements, in priority queue there is no guarantee on iteration. The only guaranteed PriorityQueue gives is that lowest or highest priority element will be on head of the queue. So when you call remove() or poll() method, you will get this element and next on priority will acquire the head spot. Like other collection classes which provides sorting, PriorityQueue also uses Comparable and Comparator interface for priority.  when you add or remove elements from PriorityQueue, other elements are compared to each other to put highest/lowest priority element at head of the queue.  priority queue data structure is internally implemented using binary heap data structure, which allows constant time access to maximum and minimum element in heap by implementing max heap and min heap data structure. In these data structure root of the binary tree always contain either maximum value (max heap) or minimum value (min heap), since you have constant time access to root, you can get max or minimum value in constant time. Once this element is removed from root, next maximum/minimum is promoted to root. So, if you want to process elements in their relative priority order, you can use PriorityQueue in Java. It provides constant time access to highest or lowest priority element. Good knowledge of Java Collection framework is absolutely necessary to become an expert Java developer and if you want to become one, I suggest you to read Java Generics and Collection by Maurice Naftalin. One of the best book which extensively cover this topic and explains about almost all the collection classes available in Java till Java SE 6.
Read more »

No comments:

Post a Comment