Java Collection Framework —PriorityQueue (Queue)

When working with data structures in Java, there are times when you need to process elements in a specific order — be it the smallest first or based on custom priority rules. This is where PriorityQueue comes into play. In this blog, we’ll break down what a PriorityQueue is, how it works, and how you can leverage it in your projects.

A PriorityQueue is a data structure that processes elements based on their priority rather than their insertion order. Unlike a regular queue, where elements are processed in a first-in-first-out (FIFO) manner, a PriorityQueue ensures the “highest-priority” element is always processed first.

Think of it like a VIP line at an event — people with VIP passes (higher priority) are let in before others, regardless of when they arrived.

The main inteface it implements is Queue. It is a finite sequence of elements in which:

1. insertion is allowed only at the back of the sequence;
2. removal is allowed only at the front of the sequence.

The term enqueue (or add ) is used for inserting an element at the back of a queue, dequeue (or remove) for removing the first element from a queue, and front (or element) for the first element in a queue. A queue imposes a chronological order on its elements: the first element enqueued, at the back, will eventually be the first element to be dequeued, from the front. The second element enqueued will be the second element to be dequeued, and so on. This defining property of queues is sometimes referred to as
“First Come, First Served,” “First In, First Out,” or simply FIFO.

public interface Queue<E> extends Collection<E>
{
    /**
    * Retrieves and removes the head of this queue.
    *
    * @return the head of this queue.
    * @throws NoSuchElementException if this queue is empty.
    */
    E remove();
    /**
    * Retrieves, but does not remove, the head of this queue.
    *
    * @return the head of this queue.
    * @throws NoSuchElementException if this queue is empty.
    */
    E element();
} // interface Queue

It also inherits add method from the Collection interface:

/**
* Ensures that this collection contains the specified element.
*
* @param element: element whose presence in this collection is to be ensured.
* @return true if this collection changed as a result of the call; otherwise, false.
*
* @throws ClassCastException class of the specified element prevents it
*
from being added to this collection.
* @throws NullPointerException if the specified element is null and this
*
collection does not support null elements.
*
*/
boolean add (E element);

In Java, the PriorityQueue class is part of the java.util package. It's implemented as a min-heap by default, meaning the smallest element is always at the head of the queue. You can also define custom priority rules using a comparator.

Get Bolot Kasybekov’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

So let’s dive into each important characteristics:

1. Dynamic Size

• A PriorityQueue dynamically adjusts its size as elements are added or removed. Unlike arrays, you don't need to define its size beforehand.
• This makes it flexible and memory-efficient, as it grows only when required.

2. Ordering

• By default, a PriorityQueue orders its elements in their natural order, which is determined by the element's implementation of the Comparable interface. For example, numbers are ordered from smallest to largest, and strings are ordered lexicographically.
• If you need a custom order, you can supply a Comprator during the queue's initialization. For instance

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

Not Thread-Safe

• A regular PriorityQueue is not thread-safe, meaning concurrent access by multiple threads can result in unpredictable behavior or corrupted data.
• To handle thread safety, you can use PriorityBlockingQueue, which is a thread-safe alternative provided in the java.util.concurrent package. It supports concurrent access while maintaining priority order.
• Example of PriorityBlockingQueue:

PriorityBlockingQueue<Integer> safeQueue = new PriorityBlockingQueue<>();
safeQueue.offer(5);
safeQueue.offer(10);

This ensures that multiple threads can safely add or remove elements.

Real-world example using PriorityQueue:

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

public class CustomPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        maxHeap.add(10);
        maxHeap.add(5);
        maxHeap.add(20);

        System.out.println("PriorityQueue (Max-Heap): " + maxHeap);

        while (!maxHeap.isEmpty()) {
            System.out.println("Processing: " + maxHeap.poll());
        }
    }
}

Why These Characteristics Matter

• Dynamic size simplifies memory management and allows for queues of unpredictable lengths.
• Custom ordering makes the queue versatile for scenarios like job scheduling, pathfinding algorithms, or event handling.
• Thread safety considerations highlight the need to pick the correct type of queue depending on the use case — single-threaded or multi-threaded environments.