Java Priority Queue Example -PriorityQueue

August 19, 2018 Sushil Singh

Java Priority Queue Example -PriorityQueue

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at the time of queue creation. A priority queue does not permit null elements. Priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

Default capacity of PriorityQueue is 11. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. Furthermore if you need ordered traversal, consider using Arrays.sort(pq.toArray()). Also PriorityQueue is not synchronized and should not be used in multi-threaded scenario where threads access it concurrently. Hence instead use the thread-safe java.util.concurrent.PriorityBlockingQueue class.

Constructors of PriorityQueue class

PriorityQueue(): Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.
PriorityQueue(Collection c): Creates a PriorityQueue containing the elements in the specified collection.
PriorityQueue(int initialCapacity): Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
PriorityQueue(int initialCapacity, Comparator comparator): Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
PriorityQueue(Comparator comparator): Creates a PriorityQueue with the default initial capacity and whose elements are ordered according to the specified comparator.
PriorityQueue(PriorityQueue c): Creates a PriorityQueue containing the elements in the specified priority queue.
PriorityQueue(SortedSet c): Creates a PriorityQueue containing the elements in the specified sorted set.

Methods under Queue

add() – This method is used to add elements at the end of Queue.
peek() – This method is used to view the head of the element of queue without removing from queue. It returns null if the queue is empty.
element() – This method is similar to peek(). This method throws NoSuchElementException if the queue is empty.
remove() – This method removes and returns head element of the queue. Also throws NoSuchElementException if the queue is empty.
poll() – It removes and returns head element of the queue. It returns null if the queue id empty.

As shown in above picture Natural ordering of PriorityQueue allows its elements to be removed in sorted ascending order as per compareTo() method. So, while removing element in the PriorityQueue, the least element according to the specified ordering is removed first. If PriorityQueue is of type String then based on alphabetical order.

PriorityQueue Usage:

Let’s create a Priority Queue of integers and after adding the integers, we’ll remove them one by one from the priority queue and see how the smallest integer is removed first followed by the next smallest integer and so on.


import java.util.PriorityQueue; 
import java.util.Queue;

public class PriorityQueueExample {
public static void main(String[] args) { 
    Queue&amp;lt;Integer&gt; pQueue = new PriorityQueue&amp;lt;&gt;(); 
    pQueue.add(900); 
    pQueue.add(100); 
    pQueue.add(700); 
    pQueue.add(200); 
    // Remove items from the PriorityQueue 
    while (!pQueue.isEmpty()) {
        System.out.println(pQueue.remove()); 
    } 
} 
}

import java.util.PriorityQueue;

import java.util.Queue;

public class PriorityQueueExample {

public static void main(String[] args) {

Queue&lt;Integer> pQueue = new PriorityQueue&lt;>();

pQueue.add(900);

pQueue.add(100);

pQueue.add(700);

pQueue.add(200);

// Remove items from the PriorityQueue

while (!pQueue.isEmpty()) {

System.out.println(pQueue.remove());

}

#Output:

100

200

700

900

Priority Queue of user defined objects

In this example, we will see how to create a priority queue of user defined objects/class.

As we have see above as priority queue needs to compare its elements and order them accordingly, the user defined class must implement the Comparable interface default sorting behavior, or you must provide a Comparator while creating the priority queue. We will try to understand it by creating a Priority Queue of Employee class.

Using Comparable Interface:

The Employee class implements the Comparable interface and compares two employees by their salary.

Employee.Java


package com.learningsolo.java.sample;
import java.util.Objects;

public class Employee implements Comparable&amp;lt;Employee&gt; {
private String name;
private double salary;

public Employee(String name, double salary) {
    this.name = name;
    this.salary = salary;
}
@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Employee employee = (Employee) o;
    return Double.compare(employee.salary, salary) == 0 &amp;amp;&amp;amp;
            Objects.equals(name, employee.name);
}

@Override
public int hashCode() {
    return Objects.hash(name, salary);
}

@Override
public String toString() {
    return "Name:"+name+" Salary:"+salary;
}

/**
 * @param employee
 * @return 
 */
@Override
public int compareTo(Employee employee) {
    if(this.getSalary() &gt; employee.getSalary()) {
        return 1;
    } else if (this.getSalary() == employee.getSalary()) {
        return 0;
    } else {
        return -1;
    }
}
public String getName() {
    return name;
}
public void setName(String name) {
    this.name = name;
}
public double getSalary() {
    return salary;
}
public void setSalary(double salary) {
    this.salary = salary;
}
}

package com.learningsolo.java.sample;

import java.util.Objects;

public class Employee implements Comparable&lt;Employee> {

private String name;

private double salary;

public Employee(String name, double salary) {

this.name = name;

this.salary = salary;

}

@Override

public boolean equals(Object o) {

if (this == o) return true;

if (o == null || getClass() != o.getClass()) return false;

Employee employee = (Employee) o;

return Double.compare(employee.salary, salary) == 0 &amp;&amp;

Objects.equals(name, employee.name);

}

@Override

public int hashCode() {

return Objects.hash(name, salary);

}

@Override

public String toString() {

return "Name:"+name+" Salary:"+salary;

}

/**

* @param employee

* @return

@Override

public int compareTo(Employee employee) {

if(this.getSalary() > employee.getSalary()) {

return 1;

} else if (this.getSalary() == employee.getSalary()) {

return 0;

} else {

return -1;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public double getSalary() {

return salary;

}

public void setSalary(double salary) {

this.salary = salary;

}

PriorityQueueExample.java


package com.learningsolo.java.sample;

import java.util.PriorityQueue;
public class PriorityQueueExample {

public static void main(String[] args) {
    PriorityQueue&amp;lt;Employee&gt; employeeQ = new PriorityQueue&amp;lt;&gt;();

    employeeQ.add(new Employee("John", 10000.00));
    employeeQ.add(new Employee("Rachel", 50500.00));
    employeeQ.add(new Employee("Roger", 120000.00));
    employeeQ.add(new Employee("Newton", 365000.00));
    employeeQ.add(new Employee("Ryan", 450030.00));

    while(!employeeQ.isEmpty()){
        System.out.println(employeeQ.remove());
    }
}
}

package com.learningsolo.java.sample;

import java.util.PriorityQueue;

public class PriorityQueueExample {

public static void main(String[] args) {

PriorityQueue&lt;Employee> employeeQ = new PriorityQueue&lt;>();

employeeQ.add(new Employee("John", 10000.00));

employeeQ.add(new Employee("Rachel", 50500.00));

employeeQ.add(new Employee("Roger", 120000.00));

employeeQ.add(new Employee("Newton", 365000.00));

employeeQ.add(new Employee("Ryan", 450030.00));

while(!employeeQ.isEmpty()){

System.out.println(employeeQ.remove());

}

#Output:

Name:John Salary:10000.0
Name:Rachel Salary:50500.0
Name:Roger Salary:120000.0
Name:Newton Salary:365000.0
Name:Ryan Salary:450030.0

Name:John Salary:10000.0

Name:Rachel Salary:50500.0

Name:Roger Salary:120000.0

Name:Newton Salary:365000.0

Name:Ryan Salary:450030.0

As you can see in above result elements under PriorityQueue is in ascending order while we try to access/remove elements from it.

Using Comparator Interface:

We will see Priority Queue implementation for Employee class using comparator interface. Comparator interface provides multiple sorting sequences.

Employee.Java

package com.learningsolo.java.sample;
import java.util.Objects;

public class Employee{

private String name;
private int salary;

public Employee(String name, int salary) {
    this.name = name;
    this.salary = salary;
}
@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Employee employee = (Employee) o;
    return Integer.compare(employee.salary, salary) == 0 &amp;amp;&amp;amp;
            Objects.equals(name, employee.name);
}

@Override
public int hashCode() {
    return Objects.hash(name, salary);
}

@Override
public String toString() {
    return "Name:"+name+" Salary:"+salary;
}

/**
 * @param employee
 * @return 
 */
@Override
public int compareTo(Employee employee) {
    if(this.getSalary() &gt; employee.getSalary()) {
        return 1;
    } else if (this.getSalary() == employee.getSalary()) {
        return 0;
    } else {
        return -1;
    }
}
public String getName() {
    return name;
}
public void setName(String name) {
    this.name = name;
}
public int getSalary() {
    return salary;
}
public void setSalary(int salary) {
    this.salary = salary;
}
}

package com.learningsolo.java.sample;

import java.util.Objects;

public class Employee{

private String name;

private int salary;

public Employee(String name, int salary) {

this.name = name;

this.salary = salary;

}

@Override

public boolean equals(Object o) {

if (this == o) return true;

if (o == null || getClass() != o.getClass()) return false;

Employee employee = (Employee) o;

return Integer.compare(employee.salary, salary) == 0 &amp;&amp;

Objects.equals(name, employee.name);

}

@Override

public int hashCode() {

return Objects.hash(name, salary);

}

@Override

public String toString() {

return "Name:"+name+" Salary:"+salary;

}

/**

* @param employee

* @return

@Override

public int compareTo(Employee employee) {

if(this.getSalary() > employee.getSalary()) {

return 1;

} else if (this.getSalary() == employee.getSalary()) {

return 0;

} else {

return -1;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public int getSalary() {

return salary;

}

public void setSalary(int salary) {

this.salary = salary;

}

MySalaryComparator.java


package com.learningsolo.java.sample;
import java.util.Comparator;

public class MySalaryComparator implements Comparator{

@Override
public int compare(Employee o1, Employee o2) {
    if(o1.getSalary() &gt; o2.getSalary()) {
        return 1;
    } else if (o1.getSalary() == o2.getSalary()) {
        return 0;
    } else {
        return -1;
    }
}
}

package com.learningsolo.java.sample;

import java.util.Comparator;

public class MySalaryComparator implements Comparator{

@Override

public int compare(Employee o1, Employee o2) {

if(o1.getSalary() > o2.getSalary()) {

return 1;

} else if (o1.getSalary() == o2.getSalary()) {

return 0;

} else {

return -1;

}

PriorityQueueExample.java


package com.learningsolo.java.sample;
import java.util.PriorityQueue;

public class PriorityQueueExample {

public static void main(String[] args) {
    PriorityQueue&amp;lt;Employee&gt; employeeQ = new PriorityQueue&amp;lt;&gt;(new MySalaryComparator());

    employeeQ.add(new Employee("John", 10000));
    employeeQ.add(new Employee("Rachel", 50500));
    employeeQ.add(new Employee("Roger", 120000));
    employeeQ.add(new Employee("Newton", 365000));
    employeeQ.add(new Employee("Ryan", 450030));

    while(!employeeQ.isEmpty()){
        System.out.println(employeeQ.remove());
    }
}
}

package com.learningsolo.java.sample;

import java.util.PriorityQueue;

public class PriorityQueueExample {

public static void main(String[] args) {

PriorityQueue&lt;Employee> employeeQ = new PriorityQueue&lt;>(new MySalaryComparator());

employeeQ.add(new Employee("John", 10000));

employeeQ.add(new Employee("Rachel", 50500));

employeeQ.add(new Employee("Roger", 120000));

employeeQ.add(new Employee("Newton", 365000));

employeeQ.add(new Employee("Ryan", 450030));

while(!employeeQ.isEmpty()){

System.out.println(employeeQ.remove());

}

#Output:

Name:John Salary:10000
Name:Rachel Salary:50500
Name:Roger Salary:120000
Name:Newton Salary:365000
Name:Ryan Salary:450030

Name:John Salary:10000

Name:Rachel Salary:50500

Name:Roger Salary:120000

Name:Newton Salary:365000

Name:Ryan Salary:450030

Summary:

Below are key points regarding Priority Queue worth noting.

PriorityQueue doesn’t allow null elements, if you try to add null, it will throw java.lang.NullPointerException.
Iterator returned by PriorityQueue doesn’t guarantee any ordering while traversal its elements.
PriorityQueue is not synchronized, if thread-safety is requirement use java.util.concurrent.PriorityBlockingQueue.

Happy Leaning. See you next time !