Priority Queue Class in Java

The Priority Queue class in Java is an essential data structure from the Java Collections Framework. Unlike a normal queue that follows the FIFO principle, a priority queue processes elements based on their priority. This makes it extremely useful in real-world applications such as task scheduling, CPU process management, and shortest path algorithms.

What Is a Priority Queue in Java?

A priority queue is a queue-based data structure where each element is assigned a priority. Elements with higher priority are retrieved before elements with lower priority, regardless of insertion order.

Key Characteristics of Java Priority Queue

• Orders elements based on priority
• Implements the Queue interface
• Part of java.util package
• Uses natural ordering by default
• Does not allow null elements

Why Use Priority Queue in Java?

The Priority Queue class in Java is ideal when the processing order of elements matters more than the order of insertion.

Real-World Use Cases

• Task scheduling systems
• CPU and process scheduling
• Dijkstra’s shortest path algorithm
• Event-driven simulations
• Huffman coding and compression algorithms

Internal Working of Priority Queue

Internal Working of Priority Queue

The PriorityQueue class in Java is implemented using a binary heap, which ensures that the element with the highest priority is always at the head of the queue. By default, Java uses a min-heap, meaning the smallest element (according to natural ordering or a comparator) is retrieved first.

Heap Structure

• A binary heap is a complete binary tree where each parent node is smaller (min-heap) or larger (max-heap) than its children.
• Insertion and removal operations are performed in O(log n) time.
• The head element (highest priority) can be accessed in O(1) time.
• Heap is maintained automatically when elements are added or removed.

How Operations Work Internally

Min-Heap vs Max-Heap

• Min-Heap: Head is the smallest element. Default in Java PriorityQueue.
• Max-Heap: Head is the largest element. Can be created using Comparator.reverseOrder() or a custom comparator.

Visual Representation

For a min-heap with elements [10, 20, 15, 30, 40]:

📄

        10
       /  \
     20    15
    /  \
   30   40

Here, 10 is the head element with the highest priority (smallest value). When polled, 10 is removed and the heap rearranges to maintain its properties.

Java PriorityQueue internally uses a binary heap data structure.

Heap Properties

• Default implementation is Min Heap
• Insertion and deletion take O(log n) time
• Accessing the head element takes O(1) time

Creating a Priority Queue in Java

Simple Priority Queue Example

📄

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(25);
        pq.add(10);
        pq.add(30);

        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
    }
}

This example demonstrates how the smallest element is always retrieved first due to natural ordering.

Creating a Max Priority Queue

Using Comparator

📄

import java.util.PriorityQueue;
import java.util.Collections;

public class MaxPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq =
            new PriorityQueue<>(Collections.reverseOrder());

        pq.add(5);
        pq.add(20);
        pq.add(15);

        System.out.println(pq.poll());
    }
}

This configuration turns the PriorityQueue into a Max Heap.

Priority Queue with Custom Objects

Task Scheduling Example

📄

import java.util.PriorityQueue;

class Task implements Comparable<Task> {
    int priority;
    String name;

    Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    public int compareTo(Task t) {
        return this.priority - t.priority;
    }
}

public class TaskManager {
    public static void main(String[] args) {
        PriorityQueue<Task> tasks = new PriorityQueue<>();

        tasks.add(new Task("Backup", 1));
        tasks.add(new Task("Email", 3));
        tasks.add(new Task("Report", 2));

        while (!tasks.isEmpty()) {
            System.out.println(tasks.poll().name);
        }
    }
}

Important Methods of PriorityQueue

Priority Queue vs Normal Queue

Best Practices

• Always define comparator logic clearly
• Avoid relying on iteration order
• Use PriorityBlockingQueue for multithreading

Frequently Asked Questions

Is Java PriorityQueue sorted?

Only the head element is guaranteed to be sorted. The remaining elements are partially ordered.

Does PriorityQueue allow duplicates?

Yes, duplicate elements are allowed.

Is PriorityQueue thread-safe?

No, it is not thread-safe by default.

Can PriorityQueue store custom objects?

Yes, custom objects can be stored using Comparable or Comparator.

When should I use PriorityQueue?

Use it when you need fast access to the highest or lowest priority element.

Conclusion

The Priority Queue class in Java is a powerful data structure designed for priority-based processing. With its heap-based implementation and flexible ordering mechanisms, it is widely used in real-world Java applications. Understanding how it works will help you design efficient and scalable systems.