Mastering PriorityQueue in Java: Use Cases, Internals & Custom Comparators

Before diving into PriorityQueue, it’s important to first understand the concept of heaps in Java.

Heap

A heap is a special kind of tree structure used to store data. It follows a simple rule: in a max-heap, parents are always bigger than or equal to their children; in a min-heap, parents are always smaller than or equal to their children.

Note:- Heaps are usually stored in arrays, even though we think of them as binary trees. You can picture a heap as a tree, but behind the scenes, it’s just an array arranged in a way that keeps the heap’s rules in place.

---

Heap Diagram

Here is a min heap structure represented as both a tree and an array.

The diagram shows two types of heaps — Max-Heap on the left and Min-Heap on the right.

1. Max-Heap

   • The number at the top (root) is always the biggest.

   • As you move down the tree, each parent number is bigger than or equal to its children.

   • The array below the tree shows how the heap is actually stored in memory.

2. Min-Heap

   • The number at the top (root) is always the smallest.

   • As you move down the tree, each parent number is smaller than or equal to its children.

   • The array below shows the same heap stored in memory.

Why arrays?
Even though heaps look like trees, they’re stored as arrays because it’s faster and easier for a computer to manage them that way. The tree structure is just a visual aid to understand the rules.

---

How Heap Works

• A heap is not a sorted list — it’s a special structure where it follows a special rule called the heap property (like always keeping the smallest number at the top in a min-heap), but the rest of the numbers aren’t sorted in order.

• The children of any element at index i are found at:

  • Left child → 2 * i + 1

  • Right child → 2 * i + 2

• The parent of a child at index i is found at:

  • Parent → (i - 1) / 2

---

Heap Implementation in Java (Simple Explanation)

When you create a heap in Java, you need to make sure it always follows the heap property — a rule that keeps the structure organised. To do this, there are some important operations you should know:

1. Insert

• Add the new element at the end of the heap (at the next empty spot).

• Then, compare it with its parent and “bubble it up” until everything is in the right order again.

• Time complexity: O(log n) — because the element moves up the tree, which has height log n.

2. Extract (Remove the root)

• Swap the root element (the top one) with the last element.

• Remove the last element (which was the root).

• Then, “bubble down” the new root element to its correct place to keep the heap property.

• Time complexity: O(log n) — because the element moves down the tree.

---

import java.util.ArrayList;

class MinHeap {
    private ArrayList<Integer> heap;

    // Initialize an empty heap
    public MinHeap() {
        heap = new ArrayList<>();
    }

    // Get parent index of given node index
    private int getParentIndex(int childIndex) {
        return (childIndex - 1) / 2;
    }

    // Get left child index of given node index
    private int getLeftChildIndex(int parentIndex) {
        return 2 * parentIndex + 1;
    }

    // Get right child index of given node index
    private int getRightChildIndex(int parentIndex) {
        return 2 * parentIndex + 2;
    }

    // Swap elements at two indices
    private void swapElements(int index1, int index2) {
        int temp = heap.get(index1);
        heap.set(index1, heap.get(index2));
        heap.set(index2, temp);
    }

    // Add a new value to the heap and fix the heap property by moving it up
    public void add(int value) {
        heap.add(value);
        int currentIndex = heap.size() - 1;

        // Uncomment for step-by-step insertion debug
        // System.out.println("Inserted " + value + " at index " + currentIndex);

        while (currentIndex > 0 && 
                heap.get(currentIndex) < heap.get(getParentIndex(currentIndex))) {
            swapElements(currentIndex, getParentIndex(currentIndex));
            currentIndex = getParentIndex(currentIndex);

            // System.out.println("Swapped with parent, current index now " + currentIndex);
        }
    }

    // Remove and return the smallest value from the heap (the root)
    public int removeMin() {
        if (heap.isEmpty()) {
            throw new RuntimeException("Heap is empty");
        }

        int minValue = heap.get(0);
        int lastValue = heap.remove(heap.size() - 1);

        if (!heap.isEmpty()) {
            heap.set(0, lastValue);

            // Uncomment for step-by-step removal debug
            // System.out.println("Moved last element to root: " + lastValue);
            bubbleDown(0);
        }

        return minValue;
    }

    // Helper method to move the element at index down to fix the heap
    private void bubbleDown(int index) {
        int currentIndex = index;

        while (true) {
            int leftIndex = getLeftChildIndex(currentIndex);
            int rightIndex = getRightChildIndex(currentIndex);
            int smallestIndex = currentIndex;

            if (leftIndex < heap.size() && heap.get(leftIndex) < heap.get(smallestIndex)) {
                smallestIndex = leftIndex;
            }

            if (rightIndex < heap.size() && heap.get(rightIndex) < heap.get(smallestIndex)) {
                smallestIndex = rightIndex;
            }

            if (smallestIndex == currentIndex) {
                break;
            }

            swapElements(currentIndex, smallestIndex);
            currentIndex = smallestIndex;

            // System.out.println("Swapped down to index " + currentIndex);
        }
    }

    // Check if heap is empty
    public boolean isEmpty() {
        return heap.isEmpty();
    }

    // For debugging: print the current heap array
    public void printHeap() {
        System.out.println(heap);
    }
}

public class HeapExample {
    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap();

        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(15);
        minHeap.add(40);
        minHeap.add(50);

        System.out.println("Removed min: " + minHeap.removeMin());
        System.out.println("Removed min: " + minHeap.removeMin());
    }
}

Expected Output:

Removed min: 10
Removed min: 15

---

Priority Queue

The PriorityQueue class (in java.util) is a heap-based queue that processes elements according to their priority rather than the usual FIFO (First-In-First-Out) order.

Key Features:

• Heap-based Implementation: Internally uses a priority heap for ordering.

• Ordering: Elements are arranged by their natural order (via Comparable) or a custom order (via Comparator) provided at construction.

• Dynamic Size: Automatically grows or shrinks as needed.

Note:
PriorityQueue<Integer> in Java is not a sorted list, so simply printing it won’t always show numbers in ascending order.

Here’s why:

• Internally, a PriorityQueue is backed by a heap (min-heap by default for Integer).

• The heap ensures that peek() and poll() give you the smallest element first (ascending order for Integer).

• But iteration or toString() does not guarantee sorted order — it just prints the internal array representation of the heap.

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(5);
        pq.add(1);
        pq.add(3);

        System.out.println(pq); // Might print [1, 5, 3] (not sorted)

        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " "); // Will print: 1 3 5
        }
    }
}

Key takeaway

• Printing directly → no guarantee of ascending order.

• Polling elements → guaranteed ascending order for natural-order PriorityQueue<Integer>.

---

Why Java’s PriorityQueue Isn’t Fully Sorted?

Let’s peek under the hood of Java’s PriorityQueue to see why its internal array doesn’t look sorted even though it can always give you the smallest element first.

1️⃣ Internal structure

A PriorityQueue in Java uses a binary heap (for integers, a min-heap) stored in an array.
Rules of a min-heap:

• The smallest element is at index 0 (the root).

• Each parent is smaller than its children.

• But siblings don’t have to be in any particular order.

Example of a min-heap array:

[1, 5, 3]

Heap tree view:

    1
   / \
  5   3

• Root 1 is smallest.

• But 5 (left child) and 3 (right child) are not sorted with each other — they just satisfy the heap property relative to the root.

---

2️⃣ Why printing gives “weird” order

When you do:

System.out.println(pq);

Java just prints the backing array of the heap.
It doesn’t sort it — it’s showing the “heapified” state:

• Internal array is partially ordered (heap property), not fully sorted.

• So you might see [1, 5, 3], [1, 2, 8, 5, 3], etc.

---

3️⃣ But poll() always works in ascending order

When you call:

pq.poll();

• It removes the root (smallest element).

• It replaces the root with the last element in the array.

• Then it “heapifies down” to restore the min-heap property.

• Repeat this, and you’ll get all elements in ascending order.

---

4️⃣ Visual Example

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(3);
System.out.println(pq); // [1, 5, 3] (not sorted)

while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");
}
// Output: 1 3 5

---

💡 Think of it like this:
A heap is like a "priority seating" system — the VIP (smallest element) is always in the front seat,
but the rest of the guests can be scattered in any order behind them.

---

Deep dive with more numbers

Let’s go messy and take 7 numbers so you can see how a PriorityQueue<Integer>’s internal array can look totally unsorted while still producing sorted output via poll().

We’ll insert:
5, 1, 3, 2, 8, 7, 4

---

Step 0 — Empty heap

(empty)

---

Step 1 — Add 5

5

Array: [5]

---

Step 2 — Add 1

• Goes as left child of 5.

• 1 < 5 → swap.

  1
 /
5

Array: [1, 5]

---

Step 3 — Add 3

• Goes as right child of 1.

• 3 > 1 → no swap.

    1
   / \
  5   3

Array: [1, 5, 3]

---

Step 4 — Add 2

• Goes as left child of 5.

• Compare 2 < 5 → swap.

    1
   / \
  2   3
 /
5

Array: [1, 2, 3, 5]

---

Step 5 — Add 8

• Goes as right child of 2.

• 8 > 2 → no swap.

    1
   / \
  2   3
 / \
5   8

Array: [1, 2, 3, 5, 8]

---

Step 6 — Add 7

• Goes as left child of 3.

• 7 > 3 → no swap.

    1
   / \
  2   3
 / \  /
5   8 7

Array: [1, 2, 3, 5, 8, 7]

---

Step 7 — Add 4

• Goes as right child of 3.

• Compare 4 > 3 → no swap.

    1
   / \
  2   3
 / \  / \
5  8 7   4

Array: [1, 2, 3, 5, 8, 7, 4]

---

🔍 Important Observation:
If you System.out.println(pq) here, you’ll see something like:

[1, 2, 3, 5, 8, 7, 4]

This is not sorted — it’s just the internal array view.

---

Now the magic when polling:

1. Poll → 1 → heapify → [2, 4, 3, 5, 8, 7]

2. Poll → 2 → heapify → [3, 4, 7, 5, 8]

3. Poll → 3 → heapify → [4, 5, 7, 8]

4. Poll → 4 → heapify → [5, 8, 7]

5. Poll → 5 → heapify → [7, 8]

6. Poll → 7 → heapify → [8]

7. Poll → 8 → heapify → []

Output sequence: 1 2 3 4 5 7 8 ✅ sorted.

---

Custom Comparator - Defining Your Own Order in PriorityQueue

In Java, you can define the sorting order of a PriorityQueue by passing a custom comparator to its constructor.

By default:

• PriorityQueue<Integer> sorts in ascending order (min-heap).

• If you want descending order (max-heap) or any custom rule, you define it with a comparator.

---

Example 1 — Ascending order (default)

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(10);
pq.add(3);

System.out.println(pq); // order in heap form, not necessarily sorted
System.out.println(pq.poll()); // 1
System.out.println(pq.poll()); // 3
System.out.println(pq.poll()); // 5
System.out.println(pq.poll()); // 10

---

Example 2 — Descending order

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // max-heap
pq.add(5);
pq.add(1);
pq.add(10);
pq.add(3);

System.out.println(pq.poll()); // 10
System.out.println(pq.poll()); // 5
System.out.println(pq.poll()); // 3
System.out.println(pq.poll()); // 1

---

Example 3 — Custom rule

Say you want smallest even numbers first, then odd numbers:

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
    if (a % 2 == 0 && b % 2 != 0) return -1; // even before odd
    if (a % 2 != 0 && b % 2 == 0) return 1;  // odd after even
    return a - b; // normal ascending within each group
});

pq.add(5);
pq.add(2);
pq.add(8);
pq.add(1);
pq.add(7);

while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " "); // 2 8 1 5 7
}

---

Real Time Use Cases of Priority Queue

Below are some real-life relatable examples for PriorityQueue use cases that you can drop near the end of your article:

1. Task Scheduling – Like a hospital emergency room where the most critical patients are treated first.

2. Event Simulation – Like a movie theater queue where people with VIP passes get seated first.

3. Dijkstra’s Algorithm – Like finding the fastest route on Google Maps where the nearest unexplored turn is always checked first.

4. Huffman Encoding – Like compressing a text file by giving shorter codes to frequently used characters.

5. Job Processing – Like an online food delivery app where urgent or high-value orders are prepared first.

Thank you for reading!

If you found it valuable, hit a like ❤️ and consider subscribing for more such content every week.

If you have any questions or suggestions, leave a comment.