PiorityQueue(=belongs to the Java Collections Framework) is an unbounded Queue, which is based on priority heap and it is an implementation of Queue interface. It can be used to keep elements in a particular order, according to their natural order (=Comparable) or custom order defined by Comparator interface based on each element’s priority.
PriorityQueue is not synchronized i.e. it cannot be safely shared between multiple threads. To avoid the Concurrent Modification Exception, PriorityBlockingQueue(= thread-safe) can be used in multithreaded environment.
Priority queue provides O(log(n)) time performance for common enqueing and dequeing methods e.g. offer(), poll() and add(), but constant time for retrieval methods e.g. peek() and element().
It was introduced in JDK 1.5.
Java PriorityQueue key points:
1. A Comparator can be provided in the constructor when instantiating a PriorityQueue. Then the order of the items in the Queue will be decided based on the Comparator provided.
If a Comparator is not provided, then the natural order (Comparable) of the Collection will be used to order the elements.
2. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).
3. null is not allowed in this Collection. It will throw the NullPointerException.
4. The head of this queue is the least element with respect to the specified ordering.
5. Ordering ties between the PriorityQueue elements are decided arbitrarily (=on the basis of random choice).
5. PriorityQueue is not synchronized. PriorityBlockingQueue is the thread-safe counterpart of PriorityQueue.
6. PriorityQueue is unbounded and it grows dynamically based on the number of elements in the Queue. It has internal capacity at any given time and it is increased as the elements are added. The policy for this internal capacity and increment is not specified or standardized.
7. The iterator() of this PriorityQueue does not guarantee for traversal of the Queue elements in any particular order.