Priority Queue in Java: A Complete Introduction

In this post, we introduce the priority queue in Java and explain the underlying concept of a heap.

What is a Priority Queue in Java?

In a priority queue, items are ordered alphabetically in ascending order, numerically in ascending order, or according to a user-defined attribute based on a custom comparator.

In a priority queue of integers, the smallest element appears at the front of the queue, while the largest element can be found at the back of the queue.

Whenever you add an element, it is inserted in its appropriate place.

How to Create a Java Priority Queue

Java offers an inbuilt priority queue that we can use.

PriorityQueue pq = new PriorityQueue();

Using Java generics, you can also constrain the priority queue only to accept a certain type of object. For example, we can tell it only to accept integers. This makes the program safer because you know exactly what type of object is contained in your priority queue and thus avoid type checking and casting.

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

You can also limit the size of the priority queue by passing an integer to the constructor.

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(3);

Now the priority queue can contain a

Adding and Removing Items in a Priority Queue

You add an item to a priority queue using the add or the offer method. You can use both, but the add method will throw an exception if you are trying to add an item to a size-limited queue that is already full.

        pq.offer(1);
        pq.add(3);
        pq.add(2);

Next, we retrieve the elements from the queue using either the remove or the poll method. Remove will throw an error if called on an empty queue while poll will not.

pq.remove();
pq.remove();

If we call these methods in succession and print each element to the console, we see that they are retrieved numerically in ascending order even though they were not added in that order.

Ordering a Java Priority Queue With Custom Objects

You can add any type of Java object to a priority queue. In the case of numbers or strings, Java applies numerical or alphabetic ordering. But how does Java know how to order the objects in the priority queue.

Let’s say we have a custom student object. Each student has a name and a number.

public class Student{
    int number;
    String name;

    public Student(int number, String name) {
        this.number = number;
        this.name = name;
    }

    public int getNumber() {
        return number;
    }

    public String getName() {
        return name;
    }

}

Next, we instantiate a few students and create a priority queue that accepts objects of type student.

PriorityQueue<Student> pq = new PriorityQueue<Student>();

Student student1 = new Student(1, "Lucy");
Student student2 = new Student(2, "John");
Student student3 = new Student(3, "Francis");
Student student4 = new Student(3, "Anne");

If we try to add a student to the priority queue, we’ll get an error

The error tells us that objects are not comparable. Java doesn’t know based on what attributes it should order the items. To rectify this, you need to create a comparator that tells the priority queue how to order items.

We create a comparator that orders students according to their number in ascending order.

Comparator<Student> studentComparator = new Comparator<Student>() {
    @Override
    public int compare(Student s1, Student s2) {
        return s1.getNumber() - s2.getNumber();
    }
};

We pass the comparator as an argument to the priority queue constructor, and now we should be able to add custom objects.

PriorityQueue<Student> pq = new PriorityQueue<Student>(studentComparator);

pq.offer(student4);
pq.add(student2);
pq.add(student3);
pq.add(student1);

There is no error anymore. If we print the items, we see that they have been ordered as expected.

Further Methods on the Java Priority Queue

Since the priority queue conforms to the Java queue interface, any queue methods can also be called on the priority queue.

Peek at Priority Queue

You can peek at the first item in the priority queue without removing it as follows.

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
pq.add(1);
pq.peek();

Check If Priority Queue Contains Items

Checking whether a priority queue contains a specific item is done via the contains method.

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
pq.add(1);
pq.contains(1);

Priority Queue Iterator

To iterate over items in the priority queue, you can instantiate an iterator.

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
pq.add(1);
pq.add(2);

Iterator iterator = pq.iterator();

while (iterator.hasNext()) {
    System.out.print(iterator.next());
}
        

Remove all elements from the Priority Queue

For deleting all elements in a priority queue, you can use the clear method.

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
pq.add(1);
pq.add(2);

pq.clear();

The Java Heap: How the Priority Queue Works under the Hood

For reordering elements according to priority, the priority queue relies on a heap.
A heap is based on a binary tree. In a binary tree, each node has two child nodes. In a max heap, child nodes always contain smaller values than their parents, while in a min-heap, child nodes contain larger values than their parents.

A new node is added at the bottom of the heap. It will percolate to its position in the tree and displace the nodes on its way.

Ultimately, the tree will rebalance.

In Java, the standard implementation of the heap is the priority queue data structures. The priority queue should suffice for almost all applications that require a heap. But if you are keen to reinvent the wheel, you can implement a heap from scratch in Java. Here is a tutorial on Geeks for Geeks that shows you how to do this.