Back to Queue, Deque & Stack
Q4Question 4 of 8

PriorityQueue vs sorted list: when to use each?

Key Concepts
  • PriorityQueue is a min-heap: only the head is guaranteed to be the minimum/maximum element; iteration order is NOT sorted
  • add() and poll() are O(log n); peek() is O(1) because the minimum is always at the root of the heap
  • A sorted list (ArrayList + sort) maintains all elements in order but insertion while maintaining sort is O(n)
  • TreeSet provides O(log n) add/remove/contains with sorted iteration, but does not allow duplicates
  • Use PriorityQueue when you repeatedly need the next highest/lowest priority element (task scheduling, event processing)
  • Use sorted list or TreeSet when you need all elements in sorted order for reports or range queries
  • PriorityQueue allows duplicates; TreeSet does not

Definition

PriorityQueue is a min-heap where only the head is guaranteed to be the smallest element; use it for repeated min/max extraction. Use a sorted list or TreeSet when you need all elements in order.
  • PriorityQueue is backed by a binary min-heap; the smallest element (by natural order or Comparator) is always at the head
  • peek() returns the minimum in O(1); poll() removes the minimum in O(log n); add() inserts in O(log n)
  • Iteration order is NOT sorted – it traverses the heap's internal array, which is only partially ordered
  • Sorted list (ArrayList + Collections.sort()) keeps all elements in order but requires O(n) insertion to maintain sort
  • TreeSet provides O(log n) sorted operations but does not allow duplicates

PriorityQueue is like a hospital emergency room. The most critical patient is always treated first (min/max at head), but the waiting room is not sorted by severity – patients sit wherever they want. A sorted list is like an alphabetical attendance register where everyone is in order and you can read from A to Z at any time.

Understanding the Concepts

What is PriorityQueue?

PriorityQueue is a queue where elements are ordered by priority rather than insertion order. The element with the highest priority (smallest value by default) is always at the head.

Internally, PriorityQueue uses a binary heap – a complete binary tree stored in an array. The minimum element is always at index 0. Adding an element places it at the end and "bubbles up" to maintain the heap property. Removing the minimum replaces it with the last element and "sinks down."

JAVA
package com.bank.service;

import java.math.BigDecimal;
import java.util.*;

public class PriorityQueueDemo {
    record Transaction(String id, BigDecimal amount, int priority) {}

    public static void main(String[] args) {
        // Min-heap: smallest priority number = highest priority
        PriorityQueue<Transaction> pq = new PriorityQueue<>(
            Comparator.comparingInt(Transaction::priority)
        );

        pq.offer(new Transaction("TXN-001", new BigDecimal("5000"), 3));    // low priority
        pq.offer(new Transaction("TXN-002", new BigDecimal("500000"), 1));  // high priority
        pq.offer(new Transaction("TXN-003", new BigDecimal("25000"), 2));   // medium

        System.out.println("Processing by priority:");
        while (!pq.isEmpty()) {
            Transaction txn = pq.poll();
            System.out.printf("  Priority %d: %s (Rs.%s)%n",
                txn.priority(), txn.id(), txn.amount());
        }
    }
}
TEXT
Processing by priority:
  Priority 1: TXN-002 (Rs.500000)
  Priority 2: TXN-003 (Rs.25000)
  Priority 3: TXN-001 (Rs.5000)

Why is iteration order NOT sorted?

The heap property guarantees only that the parent is smaller than (or equal to) its children. It does NOT guarantee that siblings are ordered, or that the array is fully sorted.

For example, a heap containing [10, 30, 20, 50, 40] is valid: 10 < 30, 10 < 20, 30 < 50, 30 < 40. But iterating the array gives 10, 30, 20, 50, 40 – not sorted.

If you need sorted iteration, you must poll elements one by one (which gives sorted order because each poll restructures the heap) or use a TreeSet.

JAVA
package com.bank.demo;

import java.util.*;

public class IterationOrderDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(50, 10, 30, 20, 40));

        // Iteration order: NOT sorted
        System.out.print("Iterator: ");
        for (int val : pq) {
            System.out.print(val + " ");
        }
        System.out.println();

        // Poll order: sorted (each poll extracts the minimum)
        System.out.print("Poll order: ");
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
        System.out.println();
    }
}
TEXT
Iterator: 10 20 30 50 40
Poll order: 10 20 30 40 50

How do you create a max-heap?

By default, PriorityQueue is a min-heap (smallest first). For a max-heap (largest first), use Comparator.reverseOrder() or a custom comparator.

JAVA
package com.bank.demo;

import java.math.BigDecimal;
import java.util.*;

public class MaxHeapDemo {
    public static void main(String[] args) {
        // Max-heap: largest amount first
        PriorityQueue<BigDecimal> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.offer(new BigDecimal("5000"));
        maxHeap.offer(new BigDecimal("500000"));
        maxHeap.offer(new BigDecimal("25000"));
        maxHeap.offer(new BigDecimal("100000"));

        System.out.println("Largest transactions first:");
        while (!maxHeap.isEmpty()) {
            System.out.println("  " + maxHeap.poll());
        }
    }
}
TEXT
Largest transactions first:
  500000
  100000
  25000
  5000

When do you use PriorityQueue vs TreeSet vs sorted list?

| Feature | PriorityQueue | TreeSet | ArrayList + sort |
|---|---|---|---|
| add | O(log n) | O(log n) | O(1) then O(n log n) sort |
| peek min | O(1) | O(log n) first() | O(1) get(0) after sort |
| poll min | O(log n) | O(log n) pollFirst() | O(n) remove(0) |
| Iteration sorted | No | Yes | Yes (after sort) |
| Duplicates | Yes | No | Yes |
| contains | O(n) | O(log n) | O(n) |
| Use case | Repeated min/max extraction | All sorted, unique | Sort once, iterate |

JAVA
package com.bank.demo;

import java.util.*;

public class ComparisonDemo {
    public static void main(String[] args) {
        // PriorityQueue: repeated min extraction
        PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(50, 10, 30, 10, 20));
        System.out.println("PQ allows duplicates, size: " + pq.size()); // 5

        // TreeSet: sorted, unique
        TreeSet<Integer> ts = new TreeSet<>(List.of(50, 10, 30, 10, 20));
        System.out.println("TreeSet unique, size: " + ts.size()); // 4
        System.out.println("TreeSet sorted: " + ts);
        System.out.println("TreeSet first: " + ts.first());

        // Sorted list: sort once, iterate
        List<Integer> list = new ArrayList<>(List.of(50, 10, 30, 10, 20));
        Collections.sort(list);
        System.out.println("Sorted list: " + list);
    }
}
TEXT
PQ allows duplicates, size: 5
TreeSet unique, size: 4
TreeSet sorted: [10, 20, 30, 50]
TreeSet first: 10
Sorted list: [10, 10, 20, 30, 50]

What are common mistakes?

Mistake 1: Iterating PriorityQueue expecting sorted order

JAVA
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(30, 10, 20));
for (int val : pq) {
    System.out.print(val + " "); // NOT 10 20 30! Heap internal order.
}
// CORRECT: poll in a loop for sorted output
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " "); // 10 20 30
}

Mistake 2: Using PriorityQueue with mutable priority

JAVA
// If you change the priority of an element after adding it,
// the heap does not re-heapify. The element stays at the wrong position.
// Fix: remove, update, re-add.

What should a senior engineer know?

  • No thread safety. PriorityQueue is not thread-safe. Use PriorityBlockingQueue for concurrent access.
  • Null not allowed. PriorityQueue rejects null elements with NullPointerException.
  • Initial capacity. Default initial capacity is 11. Set it with new PriorityQueue<>(expectedSize) to avoid resizing.
  • Used in Dijkstra's algorithm. The shortest-path algorithm uses a PriorityQueue to always process the next closest node.
  • Top-K problems. Use a max-heap of size K to find the K smallest elements in a stream. Use a min-heap of size K for the K largest.

What are common interview follow-up questions?

  • "Is PriorityQueue sorted?" – Only the head is guaranteed min/max. Iteration is NOT sorted.
  • "How do you make a max-heap?" – Use Comparator.reverseOrder().
  • "What is the time complexity of contains()?" – O(n), not O(log n).
  • "Can PriorityQueue contain duplicates?" – Yes. TreeSet cannot.

Visual Overview

DIAGRAM
  PriorityQueue (min-heap)

  Internal array: [10, 30, 20, 50, 40]

  Heap structure:        10
                       /    \
                     30      20
                    /  \
                  50    40

  peek() → 10 (O(1) – always at root)
  poll() → 10 (O(log n) – swap root with last, sink down)

  After poll(10): [20, 30, 40, 50]
                         20
                       /    \
                     30      40
                    /
                  50

  Iteration: traverses array [10, 30, 20, 50, 40] – NOT sorted!
  Poll loop: 10, 20, 30, 40, 50 – sorted!

Key Takeaway

PriorityQueue is a min-heap that guarantees only one thing: the smallest element is always at the head. Calling peek() gives you the minimum in O(1), and poll() extracts it in O(log n). But iterating the queue does not give sorted order – it traverses the heap's internal array, which is only partially ordered.

In the National Bank of India's trade processing system, Rajesh uses a PriorityQueue to process high-value transactions first. Each transaction has a priority based on its amount, and the queue always surfaces the highest-priority transaction for the next processing slot. For the monthly trade report that shows all transactions sorted by date, he uses a TreeSet because the entire collection needs to be in sorted order.

The choice is simple: if you need repeated extraction of the min/max element, use PriorityQueue. If you need all elements in sorted order for display or range queries, use TreeSet (unique) or ArrayList with sort (allows duplicates).

Remember one sentence: PriorityQueue guarantees the minimum at the head, not sorted iteration – use poll in a loop for sorted output.

---

Share
Use ← → arrow keys to navigate