Priority Queue

Photo by Meizhi Lang on Unsplash

A Priority Queue is a data structure that stores elements with associated priorities and allows efficient access to the element with the highest (or lowest) priority. In Java, it’s implemented as PriorityQueue<E> class.

Key Characteristics

1. Ordering: Elements are ordered based on their natural ordering or a custom comparator
2. Heap-based: Internally implemented as a binary heap for efficient operations
3. Not FIFO: Unlike regular queues, elements are dequeued based on priority, not insertion order
4. Thread-unsafe: Not thread-safe by default (use PriorityBlockingQueue for thread safety)

Basic Operations

// Creating a priority queue
PriorityQueue<Integer> pq = new PriorityQueue<>();

// Adding elements
pq.offer(5);  // or pq.add(5)
pq.offer(2);
pq.offer(8);
pq.offer(1);

// Peeking at highest priority element
int highest = pq.peek();  // Returns 1 (smallest by default)

// Removing highest priority element
int removed = pq.poll();  // Returns and removes 1

// Checking size
int size = pq.size();

// Checking if empty
boolean isEmpty = pq.isEmpty();

Time Complexity

• Insertion (offer/add): O(log n)
• Removal (poll/remove): O(log n)
• Peek: O(1)
• Size/isEmpty: O(1)

Get Saumya14’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Common Use Cases

1. Task Scheduling: Process tasks by priority
2. Dijkstra’s Algorithm: Finding shortest paths
3. Huffman Coding: Building Huffman trees
4. Event-driven Systems: Processing events by priority
5. Job Scheduling: CPU scheduling algorithms

Example: Task Scheduler

import java.util.*;

public class TaskScheduler {
    public static void main(String[] args) {
        PriorityQueue<Task> tasks = new PriorityQueue<>((t1, t2) -> t1.priority - t2.priority);
        
        tasks.offer(new Task("Low priority task", 3));
        tasks.offer(new Task("High priority task", 1));
        tasks.offer(new Task("Medium priority task", 2));
        
        while (!tasks.isEmpty()) {
            Task task = tasks.poll();
            System.out.println("Processing: " + task);
        }
    }
}

Important Notes

1. Null elements: PriorityQueue doesn’t allow null elements
2. Iteration order: Iterator doesn’t guarantee any specific order
3. Initial capacity: Can specify initial capacity and comparator in constructor
4. Thread safety: Use PriorityBlockingQueue for concurrent access

Priority queues are essential for algorithms that need efficient access to the “best” element based on some criteria, making them a fundamental data structure in computer science and software development.