PriorityQueue with Example

PriorityQueue is added in Collections family as part of Jav1.5. It retrieves element in sorted order irrespective of their insertion order. Sorting will be done either based on the natural order of the element or the custom order defined by the Comparable interface or the Comparator object supplied in the constructor.

Head of the PriorityQueue always contain least element with respect to specific ordering. Queue retrieval methods like remove(), poll(), peek() and element() access head of Queue, which keeps least element according to specified ordering in the queue. 

PriorityQueue does not sort out all the elements and if you iterate over the elements the retrieval order will be different. This is infact the  main difference between TreeSet and PriorityQueue in Java, Treeset keeps all elements in a particular sorted order, while PriorityQueue only keeps head in sorted order.

PriorityQueue doesn't permit null elements and trying to add null elements will result in NullPointerException.

PriorityQueue is not synchronized, use BlockingPriorityQueue for thread safety.

PriorityQueue make use of data structure called 'HEAP' - a self organizing binary tree in which add() and remove() methods cause the smallest element to save to the root, without wasting time on sorting all the elements. 
 
Complexity:
PiorityQueue 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().
 
Typical Use:
Job Scheduling.
Useful in implementation of Dijkstra algorithm in Java. 


Job Scheduling Example:
Each job has a priority. Jobs are added in random order. A highest priority job is removed from the queue.

package collections;

import java.util.PriorityQueue;

public class PriorityQueueTest {

    public static void main(String[] args){
        PriorityQueue<Job> prQueue = new PriorityQueue<Job>();
        prQueue.add(new Job("Job 5", 5));
        prQueue.add(new Job("Job 4", 4));
        prQueue.add(new Job("Job 3", 3));
        prQueue.add(new Job("Job 1", 1));
        prQueue.add(new Job("Job 2", 2));

  //prQueue.add(null); // null elements not allowed in PriorityQueue - 

// NullPointerException

        
        System.out.println("Iterating Over the Elements - No Specific Oder or Sorting");
        for(Job job: prQueue){
            System.out.println(job.getJobName());
        }
        
        System.out.println("Removing the Elements - Sorted based on the job priority - CompareTo method");
        while(!prQueue.isEmpty()){
            System.out.println(prQueue.remove().getJobName());
        }
    }
    
    private static class Job implements Comparable <Job>{

        private String jobName;
        private int jobPriority;
        
        public Job(String jobName, int priority){
            this.jobName = jobName;
            this.jobPriority = priority;
        }

        public String getJobName() {
            return jobName;
        }
        public void setJobName(String jobName) {
            this.jobName = jobName;
        }
        public int getJobPriority() {
            return jobPriority;
        }
        public void setJobPriority(int jobPriority) {
            this.jobPriority = jobPriority;
        }
        
        @Override
        public int compareTo(Job job) {
            if(this.jobPriority == job.jobPriority){
                return this.jobName.compareTo(job.jobName);
            }
            return this.jobPriority - job.jobPriority;
        }
    }
}