Priority Queue Introduction and Concept in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this PriorityQueue after insertions?

Consider the following Java code using a PriorityQueue of integers. What will be the printed order of elements when polling all elements?

DSA Java

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(30);
        pq.add(10);
        pq.add(20);
        pq.add(40);
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
    }
}

A 40 30 20 10

B 20 10 30 40

C 30 10 20 40

D 10 20 30 40

💡 Hint

Remember, Java's PriorityQueue by default is a min-heap, so it returns the smallest element first.

The PriorityQueue in Java by default orders elements in natural ascending order (min-heap). So polling returns elements from smallest to largest.

🧠 Conceptual

intermediate

Which property does a Priority Queue guarantee?

Select the property that a Priority Queue always guarantees about its elements.

A Elements are stored in the order they were inserted.

B The element with the highest priority is always accessed first.

C Elements are always sorted internally in ascending order.

D Elements are stored in a balanced binary search tree.

💡 Hint

Think about what 'priority' means in a Priority Queue.

A Priority Queue always ensures that the element with the highest priority (smallest or largest depending on implementation) is accessed first, not that all elements are sorted internally.

🔧 Debug

advanced

What error occurs when polling from an empty PriorityQueue?

Given an empty PriorityQueue pq = new PriorityQueue<>(); what happens if we call pq.poll()?

A Returns null

B Throws NoSuchElementException

C Throws NullPointerException

D Returns 0

💡 Hint

Check the Java documentation for PriorityQueue.poll() behavior on empty queue.

The poll() method returns null if the queue is empty. It does not throw an exception.

❓ Predict Output

advanced

What is the output after custom comparator PriorityQueue insertions?

Consider this Java code using a PriorityQueue with a custom comparator to reverse order. What is the printed output when polling all elements?

DSA Java

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

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        pq.add(5);
        pq.add(1);
        pq.add(3);
        pq.add(4);
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
    }
}

A 5 4 3 1

B 1 3 4 5

C 3 1 4 5

D 4 5 3 1

💡 Hint

The comparator reverses the natural order, so the largest element is polled first.

Using Comparator.reverseOrder() makes the PriorityQueue behave like a max-heap, so polling returns elements from largest to smallest.

🚀 Application

expert

How many elements remain after these PriorityQueue operations?

Given the following Java code, how many elements remain in the PriorityQueue after all operations?

DSA Java

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<>();
        pq.add("apple");
        pq.add("banana");
        pq.add("cherry");
        pq.poll();
        pq.add("date");
        pq.poll();
        pq.add("elderberry");
        pq.poll();
        System.out.println(pq.size());
    }
}

A 3

B 4

C 2

D 1

💡 Hint

Trace each add and poll operation carefully to count remaining elements.

Initially 3 elements added. Then poll removes smallest. Add one, poll removes smallest again, add one, poll removes smallest again. Final count is 2.

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