o7planning

Java PriorityQueue Tutorial with Examples

  1. PriorityQueue
  2. Examples

1. PriorityQueue

PriorityQueue is a class that implements Queue interface, so it has all the characteristics of a queue and supports all optional Collection operations. However, unlike a regular queue, elements of a PriorityQueue are sorted in ascending order based on their natural order or according to a provided Comparator (depending on the constructor used), so when a new element is inserted into PriorityQueue, it may not be in the last position.
Characteristics inherited from Queue:
  • Duplicate elements are allowed, but null elements are not allowed.
public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable
PriorityQueue is an unbounded queue. Elements are sorted in ascending order and duplicate elements are allowed.
Basically, PriorityQueue manages an array of objects (Object[]) to store its elements. The length of this array is greater than the number of elements of the queue. However, the array will be replaced by another array of greater length if necessary.
PriorityQueue constructors
PriorityQueue()    

PriorityQueue​(int initialCapacity)    

PriorityQueue​(int initialCapacity, Comparator<? super E> comparator)    

PriorityQueue​(Collection<? extends E> c)    

PriorityQueue​(Comparator<? super E> comparator)    

PriorityQueue​(PriorityQueue<? extends E> c)    

PriorityQueue​(SortedSet<? extends E> c)
  • PriorityQueue(int initialCapacity) constructor creates a PriorityQueue object with an internal array of initialCapacity size. In this case, all elements of PriorityQueue must be Comparable type to be able to compare themselves, and null elements are not allowed.
  • PriorityQueue(Comparator) constructor creates a PriorityQueue object with the default internal array size of 11. At the same time it is provided with a Comparator to compare elements with each others.
PriorityQueue is an asynchronous queue, so you shouldn't use it in a multithreading environment, use thread-safe class PriorityBlockingQueue instead.
// Methods inherited from Collection:

Iterator<E> iterator()
default Spliterator<E> spliterator()
  • Iterator obtained from PriorityQueue supports all optional methods.
  • Iterator (or Spliterator) obtained from PriorityQueue does not guarantee that it will traverse the elements in priority order. If you want to iterate through the elements in priority order, consider using Arrays.sort(priorityQueue.toArray()).

2. Examples

String is a self-comparable data type because it implements Comparable interface. So there is no need to provide a Comparator for PriorityQueue<String>.
PriorityQueueEx1.java
package org.o7planning.priorityqueue.ex;

import java.util.PriorityQueue;

public class PriorityQueueEx1 {

    public static void main(String[] args) {  
        PriorityQueue<String> queue = new PriorityQueue<>();

        queue.add("F");
        queue.add("D");
        queue.add("B");
        queue.add("A");
        queue.add("C");

        String s = null;
        
        // Retrieves and removes the head of this queue
        while((s = queue.poll())!= null)  {
            System.out.println(s);
        }
    }
}
Output:
A
B
C
D
F
For example: Customer class with fullName, loyaltyPoints properties (Full name, accumulated points when purchasing). Customers with higher loyaltyPoints will be given higher priority.
Customer.java
package org.o7planning.beans;

public class Customer implements Comparable<Customer> {
    private String fullName;
    private int loyaltyPoints;

    public Customer(String fullName, int pointOfPurchase) { //
        this.fullName = fullName;
        this.loyaltyPoints = pointOfPurchase;
    }

    public String getFullName() {
        return fullName;
    }

    public int getLoyaltyPoints() {
        return loyaltyPoints;
    }

    @Override
    public int compareTo(Customer other) {
        if (other == null) {
            return -1; // this < other
        }
        int delta = this.loyaltyPoints - other.loyaltyPoints;
        if (delta != 0) {
            return - delta;
        }  
        return this.fullName.compareTo(other.fullName);
    }
}
PriorityQueueEx2.java
package org.o7planning.priorityqueue.ex;

import java.util.PriorityQueue;

import org.o7planning.beans.Customer;

public class PriorityQueueEx2 {

    public static void main(String[] args) {
        Customer tom = new Customer("Tom", 200);
        Customer jerry = new Customer("Jerry", 50);
        Customer donald = new Customer("Donald", 300);
        Customer mickey = new Customer("Mickey", 30);
        Customer daffy = new Customer("Daffy", 500);
        
        PriorityQueue<Customer> queue = new PriorityQueue<>();
        
        queue.add(tom);
        queue.add(jerry);
        queue.add(donald);
        queue.add(mickey);
        queue.add(daffy);
        
        Customer currentCustomer = null;
        
        while((currentCustomer = queue.poll())!= null) { // Retrieves and removes
            System.out.println("--- Serving customer: " + currentCustomer.getFullName() + " ---");
            System.out.println("   >> Loyalty Points: " + currentCustomer.getLoyaltyPoints());
            System.out.println();
        }
    }
}
Output:
--- Serving customer: Daffy ---
   >> Loyalty Points: 500

--- Serving customer: Donald ---
   >> Loyalty Points: 300

--- Serving customer: Tom ---
   >> Loyalty Points: 200

--- Serving customer: Jerry ---
   >> Loyalty Points: 50

--- Serving customer: Mickey ---
   >> Loyalty Points: 30
Example: For elements that are not self-comparable, you need to provide a Comparator for the PriorityQueue.
PriorityQueueEx3.java
package org.o7planning.priorityqueue.ex;

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueEx3 {

    public static void main(String[] args) {

        Employee tom = new Employee("Tom", 2000);
        Employee jerry = new Employee("Jerry", 500);
        Employee donald = new Employee("Donald", 3000);
        Employee mickey = new Employee("Mickey", 2000);
        Employee daffy = new Employee("Daffy", 5000);

        PriorityQueue<Employee> queue = new PriorityQueue<>(new EmployeeComparator());

        queue.add(tom);
        queue.add(jerry);
        queue.add(donald);
        queue.add(mickey);
        queue.add(daffy);

        Employee currentEmployee = null;

        while ((currentEmployee = queue.poll()) != null) { // Retrieves and removes
            System.out.println("--- Serving employee: " + currentEmployee.getFullName() + " ---");
            System.out.println("   >> Salary: " + currentEmployee.getSalary());
            System.out.println();
        }
    }
}

class Employee {
    private String fullName;
    private int salary;

    public Employee(String fullName, int salary) {
        this.fullName = fullName;
        this.salary = salary;
    }

    public String getFullName() {
        return fullName;
    }

    public int getSalary() {
        return salary;
    }
}

class EmployeeComparator implements Comparator<Employee> {

    @Override
    public int compare(Employee o1, Employee o2) {
        if (o1 == o2) {
            return 0;
        }
        if (o1 == null) {
            return -1; // o1 < o2
        }
        if (o2 == null) {
            return 1; // o1 > o2
        }
        int s = o1.getSalary() - o2.getSalary();
        if (s != 0) {
            return s;
        }
        return o1.getFullName().compareTo(o2.getFullName());
    }
}
Output:
--- Serving employee: Jerry ---
   >> Salary: 500

--- Serving employee: Mickey ---
   >> Salary: 2000

--- Serving employee: Tom ---
   >> Salary: 2000

--- Serving employee: Donald ---
   >> Salary: 3000

--- Serving employee: Daffy ---
   >> Salary: 5000
If you want to iterate through all elements of a PriorityQueue without removing them, you can use Iterator or Spliterator, but they do not guarantee the priority order of the elements. In this case you should use Arrays.sort(priorityQueue.toArray()) or Arrays.sort(priorityQueue.toArray(),comparator).
PriorityQueueEx4.java
package org.o7planning.priorityqueue.ex;

import java.util.Arrays;
import java.util.Iterator;
import java.util.PriorityQueue;

public class PriorityQueueEx4 {

    public static void main(String[] args) {

        PriorityQueue<String> queue = new PriorityQueue<>();

        queue.add("F");
        queue.add("D");
        queue.add("B");
        queue.add("A");
        queue.add("C");

        System.out.println("--- Using Iterator: ---");
        
        Iterator<String> ite = queue.iterator();
        
        while(ite.hasNext()) {
            String e = ite.next();
            System.out.println(e);
        }
        System.out.println("--- Using Arrays.sort(queue.toArray()): ----");
        
        String[] array = new String[queue.size()];
        queue.toArray(array);
        
        Arrays.sort(array);
        
        for(String e: array) {
            System.out.println(e);
        }
    }
}
Output:
--- Using Iterator: ---
A
B
D
F
C
--- Using Arrays.sort(queue.toArray()): ----
A
B
C
D
F
Basically, in addition to the aforementioned characteristics, PriorityQueue has all the characteristics of a Queue. Queue methods and related examples are mentioned in the following article:

Java Collections Framework Tutorials

Show More

Newest Articles

Show More