PriorityQueue (Heap)

Min-Heap (Default PriorityQueue)

PriorityQueue in Java is a min-heap by default. The smallest element (based on natural ordering or Comparator) is always at the head.

Key characteristics:

• Min-heap by default (smallest first)
• O(log n) for offer/poll, O(1) for peek
• Not synchronized
• Does not allow null elements
• Backed by a balanced binary heap (array)

import java.util.*;

public class MinHeapDemo {
    public static void main(String[] args) {
        // Default min-heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(30);
        minHeap.offer(10);
        minHeap.offer(50);
        minHeap.offer(20);
        minHeap.offer(40);

        System.out.println("Min-heap (peek): " + minHeap.peek()); // 10
        System.out.println("Polling elements:");
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " "); // 10 20 30 40 50
        }
        System.out.println();

        // Strings - natural ordering (alphabetical)
        PriorityQueue<String> names = new PriorityQueue<>();
        names.offer("Charlie");
        names.offer("Alice");
        names.offer("Bob");
        System.out.println("\nAlphabetical: " + names.peek()); // Alice
        while (!names.isEmpty()) {
            System.out.print(names.poll() + " ");
        }
        System.out.println();

        // Building from array
        int[] arr = {5, 3, 8, 1, 2, 9, 4};
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : arr) {
            heap.offer(num);
        }
        System.out.println("\nSorted from heap: ");
        while (!heap.isEmpty()) {
            System.out.print(heap.poll() + " "); // 1 2 3 4 5 8 9
        }
        System.out.println();

        // Useful methods
        System.out.println("\nSize: " + heap.size());
        System.out.println("isEmpty: " + heap.isEmpty());
    }
}

How it works internally: The heap is stored as an array where for node at index i:

• Left child: 2*i + 1
• Right child: 2*i + 2
• Parent: (i-1) / 2

When you offer(), the element is placed at the end and bubbled up. When you poll(), the root is removed, the last element moves to root, and it bubbles down.

Max-Heap with Custom Comparator

To create a max-heap (largest element at head), provide a Comparator that reverses the natural ordering.

import java.util.*;

public class MaxHeapDemo {
    public static void main(String[] args) {
        // Method 1: Comparator.reverseOrder()
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.offer(30);
        maxHeap.offer(10);
        maxHeap.offer(50);
        maxHeap.offer(20);
        maxHeap.offer(40);

        System.out.println("Max-heap (peek): " + maxHeap.peek()); // 50
        System.out.println("Polling elements:");
        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " "); // 50 40 30 20 10
        }
        System.out.println();

        // Method 2: Lambda comparator
        PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>((a, b) -> b - a);
        maxHeap2.offer(30);
        maxHeap2.offer(10);
        maxHeap2.offer(50);
        System.out.println("\nLambda max-heap: " + maxHeap2.peek()); // 50

        // Method 3: Custom object sorting
        PriorityQueue<String> longestFirst = new PriorityQueue<>(
            Comparator.comparingInt(String::length).reversed()
        );
        longestFirst.offer("Hi");
        longestFirst.offer("Hello");
        longestFirst.offer("Hey");
        longestFirst.offer("Greetings");
        System.out.println("\nBy length (longest first):");
        while (!longestFirst.isEmpty()) {
            System.out.println("  " + longestFirst.poll());
        }

        // Custom class with Comparator
        class Task {
            String name;
            int priority;
            Task(String name, int priority) {
                this.name = name;
                this.priority = priority;
            }
            @Override
            public String toString() { return name + "(p" + priority + ")"; }
        }

        PriorityQueue<Task> tasks = new PriorityQueue<>(
            Comparator.comparingInt((Task t) -> t.priority)
        );
        tasks.offer(new Task("Low priority", 3));
        tasks.offer(new Task("High priority", 1));
        tasks.offer(new Task("Medium priority", 2));

        System.out.println("\nBy priority:");
        while (!tasks.isEmpty()) {
            System.out.println("  " + tasks.poll());
        }
    }
}

Common patterns:

• new PriorityQueue<>(Comparator.reverseOrder()) — max-heap
• new PriorityQueue<>((a, b) -> b - a) — max-heap (lambda)
• new PriorityQueue<>(Comparator.comparingInt(...)) — sort by int field
• .reversed() — reverse any comparator

Core Methods of PriorityQueue

Method	Time Complexity	Description
offer(e)	O(log n)	Add element to heap
poll()	O(log n)	Remove and return head (smallest)
peek()	O(1)	Return head without removing
size()	O(1)	Number of elements
isEmpty()	O(1)	Check if empty
contains(o)	O(n)	Search for element
remove(o)	O(n)	Remove specific element
clear()	O(n)	Remove all elements

import java.util.*;

public class PriorityQueueMethodsDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // offer - add element
        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        pq.offer(2);
        pq.offer(4);
        System.out.println("Heap: " + pq); // [1, 2, 3, 5, 4]

        // peek - view smallest without removing
        System.out.println("Peek: " + pq.peek()); // 1
        System.out.println("Size after peek: " + pq.size()); // 5

        // poll - remove smallest
        System.out.println("Poll: " + pq.poll()); // 1
        System.out.println("Poll: " + pq.poll()); // 2
        System.out.println("Size after polls: " + pq.size()); // 3

        // contains - O(n) search
        System.out.println("Contains 3: " + pq.contains(3)); // true
        System.out.println("Contains 1: " + pq.contains(1)); // false (was polled)

        // remove specific element
        pq.remove(3);
        System.out.println("After remove(3): " + pq); // [4, 5]

        // toArray
        Object[] array = pq.toArray();
        System.out.println("Array: " + Arrays.toString(array));

        // iterator - does NOT guarantee order!
        System.out.println("Iterator (no order guarantee):");
        for (Integer num : pq) {
            System.out.print(num + " ");
        }
        System.out.println();

        // drainTo - remove all elements efficiently
        PriorityQueue<Integer> drain = new PriorityQueue<>(Arrays.asList(1, 2, 3, 4, 5));
        List<Integer> drained = new ArrayList<>();
        drain.drainTo(drained);
        System.out.println("Drained: " + drained); // [1, 2, 3, 4, 5]
        System.out.println("Original empty: " + drain.isEmpty()); // true
    }
}

Important notes:

• poll() returns null if empty (unlike remove() which throws)
• peek() returns null if empty
• The iterator does NOT guarantee heap order — use poll() for ordered access
• drainTo() is more efficient than calling poll() in a loop

Internal Structure: Balanced Binary Heap

PriorityQueue is backed by a balanced binary heap stored as an array.

Array representation of a heap:

Index:  0  1  2  3  4  5  6
Value:  1  3  2  7  5  8  4

Tree form:
           1
         /   \
        3     2
       / \\   / \
      7   5 8   4

Formulas:

• Parent of node i: (i - 1) / 2
• Left child of node i: 2 * i + 1
• Right child of node i: 2 * i + 2

import java.util.*;

public class HeapStructureDemo {
    public static void main(String[] args) {
        // Visualize heap operations
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        // Insert elements one by one
        int[] elements = {5, 3, 8, 1, 2, 9, 4};
        for (int e : elements) {
            heap.offer(e);
            System.out.println("Added " + e + ": heap = " + heap);
        }

        System.out.println("\n--- Extracting in order ---");
        while (!heap.isEmpty()) {
            System.out.println("Poll " + heap.poll() + ": remaining = " + heap);
        }

        // Demonstrate heap property
        System.out.println("\n--- Heap property ---");
        System.out.println("Min-heap: parent <= children");
        System.out.println("For node at index i:");
        System.out.println("  parent = (i-1)/2");
        System.out.println("  left = 2*i + 1");
        System.out.println("  right = 2*i + 2");
    }
}

How offer() works (bubble up):

1. Add element at end of array
2. Compare with parent
3. If smaller than parent, swap with parent
4. Repeat until heap property is restored

How poll() works (bubble down):

1. Save root element (minimum)
2. Move last element to root
3. Compare with children
4. If larger than a child, swap with smaller child
5. Repeat until heap property is restored

Both operations are O(log n) because the tree has height log(n).

DSA Applications of PriorityQueue

PriorityQueue is essential for many algorithm patterns:

import java.util.*;

public class PriorityQueueDSA {

    // Pattern 1: Top K Elements
    public static int[] topK(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // remove smallest
            }
        }
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = minHeap.poll();
        }
        return result;
    }

    // Pattern 2: Kth Largest Element
    public static int kthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }

    // Pattern 3: Merge K Sorted Lists
    public static List<Integer> mergeKSorted(List<List<Integer>> lists) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[1])
        );
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < lists.size(); i++) {
            if (!lists.get(i).isEmpty()) {
                minHeap.offer(new int[]{i, 0});
            }
        }

        while (!minHeap.isEmpty()) {
            int[] current = minHeap.poll();
            int listIdx = current[0];
            int elemIdx = current[1];
            result.add(lists.get(listIdx).get(elemIdx));
            if (elemIdx + 1 < lists.get(listIdx).size()) {
                minHeap.offer(new int[]{listIdx, elemIdx + 1});
            }
        }

        return result;
    }

    // Pattern 4: Task Scheduler
    public static int leastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
        for (char c : tasks) freq[c - 'A']++;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        for (int f : freq) {
            if (f > 0) maxHeap.offer(f);
        }
        int time = 0;
        while (!maxHeap.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i <= n && !maxHeap.isEmpty(); i++) {
                temp.add(maxHeap.poll() - 1);
                time++;
            }
            for (int t : temp) {
                if (t > 0) maxHeap.offer(t);
            }
            if (!maxHeap.isEmpty()) time += n - temp.size() + 1;
        }
        return time;
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 5, 12, 2, 11};
        System.out.println("Top 3: " + Arrays.toString(topK(nums, 3)));
        System.out.println("Kth largest (k=3): " + kthLargest(nums, 3));

        List<List<Integer>> lists = Arrays.asList(
            Arrays.asList(1, 4, 7),
            Arrays.asList(2, 5, 8),
            Arrays.asList(3, 6, 9)
        );
        System.out.println("Merged: " + mergeKSorted(lists));
    }
}

Key patterns:

• Top K: Use min-heap of size K
• Kth largest: Min-heap of size K, peek is the answer
• Merge K sorted: Min-heap with indices into each list
• Median finding: Two heaps (max-heap for lower half, min-heap for upper half)