Priority Queue Introduction and Concept in DSA Java

Mental Model

A priority queue is like a line where people with higher importance get served first, not just the ones who came first.

Analogy: Imagine a hospital emergency room where patients with more serious conditions are treated before others, regardless of arrival time.

Priority Queue:
[10] -> [5] -> [3] -> null
↑ highest priority at front

Dry Run Walkthrough

Input: Insert values 3, 10, 5 into an empty priority queue

Goal: Keep the queue ordered so the highest value (priority) is always at the front

Step 1: Insert 3 into empty queue

[3] -> null

Why: Start with first element as the highest priority

Step 2: Insert 10, which is higher than 3, so place it before 3

[10] -> [3] -> null

Why: Higher priority goes to front to be served first

Step 3: Insert 5, which is less than 10 but greater than 3, so place it between 10 and 3

[10] -> [5] -> [3] -> null

Why: Keep queue ordered by priority descending

Result:

[10] -> [5] -> [3] -> null

Annotated Code

DSA Java

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

public class PriorityQueueDemo {
    public static void main(String[] args) {
        // Create a priority queue that orders elements from highest to lowest
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        // Insert elements 3, 10, 5
        pq.offer(3); // Insert 3
        pq.offer(10); // Insert 10
        pq.offer(5); // Insert 5

        // Print elements by polling (removing) from highest priority to lowest
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " -> "); // Remove and print highest priority
        }
        System.out.print("null");
    }
}

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

Create priority queue with highest value as highest priority

pq.offer(3);

Insert first element into queue

pq.offer(10);

Insert element with higher priority, queue reorders

pq.offer(5);

Insert element with middle priority, queue reorders

while (!pq.isEmpty()) { System.out.print(pq.poll() + " -> "); }

Remove and print elements from highest to lowest priority

Output

10 -> 5 -> 3 -> null

Complexity Analysis

Time: O(log n) for each insertion and removal because the priority queue maintains order using a heap structure

Space: O(n) because it stores all elements in the queue

vs Alternative: Compared to a simple queue which is O(1) for insertion but O(n) to find highest priority, priority queue is more efficient for priority-based retrieval

Edge Cases

Empty priority queue

Polling returns null or no element, no error

DSA Java

while (!pq.isEmpty()) {

Single element insertion

Element is inserted and becomes highest priority

DSA Java

pq.offer(3);

Duplicate priorities

Duplicates are allowed and served in order they appear with same priority

DSA Java

pq.offer(5);

When to Use This Pattern

When you need to always process the most important item first, not just the oldest, use a priority queue to efficiently manage order.

Common Mistakes

Mistake: Using a normal queue which serves elements in arrival order, ignoring priority
Fix: Use a priority queue data structure that orders elements by priority

Mistake: Not specifying reverse order for highest priority first in Java's PriorityQueue
Fix: Use Collections.reverseOrder() to make highest value have highest priority

Summary

A priority queue stores elements so the highest priority is always served first.

Use it when you must process items by importance, not arrival time.

The key is that the queue automatically keeps elements ordered by priority.

Practice

1. What is the main characteristic of a Priority Queue compared to a regular queue?

easy

A. Elements are dequeued based on their priority, not just order of insertion

B. Elements are always dequeued in the order they were inserted

C. It only stores elements of the same value

D. It does not allow duplicate elements

Solution

1. Step 1: Understand queue behavior

   A regular queue removes elements in the order they were added (FIFO).

2. Step 2: Understand priority queue behavior

   A priority queue removes elements based on priority, not insertion order.

3. Final Answer:

   Elements are dequeued based on their priority, not just order of insertion -> Option A

4. Quick Check:

   Priority Queue = Priority-based removal [OK]

Hint: Priority queue removes highest priority first, not oldest [OK]

Common Mistakes:

• Confusing priority queue with FIFO queue
• Thinking priority queue sorts elements permanently
• Assuming duplicates are not allowed

2. Which of the following is the correct way to declare a Priority Queue of integers in Java?

easy

A. PriorityQueue<int> pq = new PriorityQueue<>();

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

C. PriorityQueue pq = new PriorityQueue<int>();

D. PriorityQueue<Integer> pq = new PriorityQueue<int>();

Solution

1. Step 1: Use wrapper class for generics

   Java generics require wrapper classes, so use Integer, not int.

2. Step 2: Correct generic syntax

   Use diamond operator <> on the right side without type inside.

3. Final Answer:

   PriorityQueue<Integer> pq = new PriorityQueue<>(); -> Option B

4. Quick Check:

   Use wrapper Integer and diamond operator [OK]

Hint: Use wrapper classes (Integer) with generics, not primitives [OK]

Common Mistakes:

• Using primitive types (int) with generics
• Specifying type twice on right side
• Not using diamond operator

3. What will be the output of the following Java code?

import java.util.*;
public class TestPQ {
  public static void main(String[] args) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    pq.add(30);
    pq.add(10);
    pq.add(20);
    System.out.print(pq.poll() + ", " + pq.poll() + ", " + pq.poll());
  }
}

medium

A. 10, 20, 30

B. 30, 20, 10

C. 20, 10, 30

D. 10, 30, 20

Solution

1. Step 1: Understand PriorityQueue default order

   Java's PriorityQueue by default is a min-heap, so smallest element is removed first.

2. Step 2: Trace poll() calls

   Elements added: 30, 10, 20. Poll removes 10, then 20, then 30.

3. Final Answer:

   10, 20, 30 -> Option A

4. Quick Check:

   Min-heap poll order = 10, 20, 30 [OK]

Hint: PriorityQueue.poll() returns smallest element first by default [OK]

Common Mistakes:

• Assuming insertion order is preserved
• Thinking PriorityQueue is max-heap by default
• Confusing poll() with peek()

4. Identify the error in the following code snippet that uses a Priority Queue in Java:

import java.util.PriorityQueue;
public class Demo {
  public static void main(String[] args) {
    PriorityQueue pq = new PriorityQueue();
    pq.add("apple");
    pq.add(10);
    System.out.println(pq.poll());
  }
}

medium

A. PriorityQueue requires initial capacity in constructor

B. PriorityQueue must be imported from java.util.concurrent package

C. PriorityQueue cannot mix different data types like String and Integer

D. PriorityQueue does not support add() method

Solution

1. Step 1: Check PriorityQueue type safety

   Without generics, PriorityQueue stores Objects but cannot compare different types.

2. Step 2: Mixing String and Integer causes ClassCastException

   Adding both String and Integer causes runtime error when ordering elements.

3. Final Answer:

   PriorityQueue cannot mix different data types like String and Integer -> Option C

4. Quick Check:

   Mixed types cause runtime error in PriorityQueue [OK]

Hint: PriorityQueue elements must be mutually comparable [OK]

Common Mistakes:

• Ignoring type safety and mixing types
• Wrong import statement
• Assuming add() method is unsupported

5. You want to create a Priority Queue in Java that always returns the largest element first. Which of the following is the best way to achieve this?

hard

A. Use PriorityQueue<Integer> pq = new PriorityQueue<>(); and add elements normally

B. Use PriorityQueue<Integer> pq = new PriorityQueue<>(null);

C. Use PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.naturalOrder());

D. Use PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

Solution

1. Step 1: Understand default PriorityQueue order

   By default, PriorityQueue is a min-heap, so smallest element is returned first.

2. Step 2: Use reverse order comparator for max-heap behavior

   Passing Collections.reverseOrder() makes it return largest element first.

3. Final Answer:

   PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); -> Option D

4. Quick Check:

   Reverse order comparator = max-heap PriorityQueue [OK]

Hint: Use Collections.reverseOrder() to get max element first [OK]

Common Mistakes:

• Assuming default PriorityQueue is max-heap
• Passing null comparator causes NullPointerException
• Using naturalOrder() returns min element first