☕ JavaCollections Framework

PriorityQueue

PriorityQueue is an unbounded queue implementation backed by a binary heap that orders elements by priority rather than insertion order. The element with the lowest priority value (by natural ordering or a supplied Comparator) is always at the head and is the first to be removed. PriorityQueue is the standard Java implementation of the priority queue abstract data type — a fundamental structure in algorithms for task scheduling, graph shortest-path algorithms (Dijkstra, A*), and any scenario where the next item to process should be the most urgent or important rather than the oldest. This entry covers the binary heap internals, natural and custom ordering, the performance characteristics of each operation, the behaviour of iteration vs retrieval, and practical algorithmic use cases.

Binary Heap Internals and Performance

PriorityQueue is backed by a binary min-heap — a complete binary tree stored in an array where every parent's value is less than or equal to both its children's values. This heap invariant guarantees that the minimum element is always at the root (index 0), enabling O(1) peek at the minimum and O(log n) insertion and removal. The array representation of the binary heap is elegant and efficient. For an element at index i, its left child is at index 2i+1 and its right child is at 2i+2. Its parent is at (i-1)/2. No node objects, no pointers — just index arithmetic. This layout is cache-friendly: traversing the heap accesses adjacent memory addresses, fitting well into CPU caches. The absence of node objects also means no per-element memory overhead beyond the element reference itself. Insertion (offer) places the new element at the first empty position (end of the array) and sifts it up: compares with its parent and swaps if the new element has higher priority (smaller value), repeating until the invariant is restored. This sift-up operation traverses at most log n levels of the heap tree. Removal of the minimum (poll) takes the root, moves the last element to the root position, then sifts it down: compares with both children and swaps with the smaller child, repeating until the invariant is restored. Both operations are O(log n). Critically, PriorityQueue only guarantees that the head element (retrieved by peek() or poll()) is the minimum. The remaining elements are partially ordered by the heap invariant, not fully sorted. This is why iteration over a PriorityQueue does not produce elements in priority order — the iterator traverses the underlying array in storage order, not heap-sorted order. To retrieve all elements in priority order, repeatedly call poll() until the queue is empty.

Java

// ── PriorityQueue construction and basic operations ───────────────────
// Default: natural ordering (elements must be Comparable)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.offer(2);
minHeap.offer(4);

System.out.println(minHeap.peek());   // 1 — minimum, O(1)

// ── Iteration vs ordered retrieval — the critical distinction ─────────
System.out.println("Iteration (unordered):");
for (int n : minHeap) {
    System.out.print(n + " ");   // e.g. 1 2 3 5 4 — heap storage order, NOT sorted
}

System.out.println("
Ordered retrieval (poll):");
while (!minHeap.isEmpty()) {
    System.out.print(minHeap.poll() + " ");  // 1 2 3 4 5 — sorted, each poll O(log n)
}

// ── Internal heap array structure ─────────────────────────────────────
//
// After inserting 5, 1, 3, 2, 4 into a min-heap:
//
//         1           index 0 (root = minimum)
//        / //       2    3         index 1, 2
//      / //     5   4            index 3, 4
//
// Array: [1, 2, 3, 5, 4]
//
// Parent of index i:  (i-1)/2
// Left child of i:    2i+1
// Right child of i:   2i+2
//
// Insertion of 0:
// Array: [1, 2, 3, 5, 4, 0]  ← added at end
// Sift up: 0 < parent(3) → swap: [1, 2, 0, 5, 4, 3]
//          0 < parent(1) → swap: [0, 2, 1, 5, 4, 3]  ← heap restored

// ── Performance summary ───────────────────────────────────────────────
// offer(e)    O(log n)   insert + sift up
// poll()      O(log n)   remove min + sift down
// peek()      O(1)       read root element
// remove(o)   O(n)       linear scan + O(log n) sift — avoid in hot paths
// contains(o) O(n)       linear scan
// size()      O(1)       field read
// toArray()   O(n)       copy array
// All other Collection methods: O(n)

Natural Ordering and Custom Comparators

PriorityQueue uses natural ordering by default, which requires elements to implement Comparable. The element with the smallest natural-order value is at the head — integers ordered numerically, strings lexicographically, dates chronologically. For custom ordering or for types that do not implement Comparable, a Comparator is provided to the constructor. Reversing the ordering — creating a max-heap where the largest element is at the head — is done with Comparator.reverseOrder() for natural-order types, or by reversing a custom comparator. There is no separate MaxPriorityQueue class; ordering direction is entirely controlled by the Comparator. Comparator composition with Comparator.comparing() and thenComparing() enables multi-field priority. A task scheduler might order tasks by priority level (highest priority first), breaking ties by submission time (earliest first), and further breaking ties by task name alphabetically. This three-level ordering is expressed cleanly with the Comparator factory methods. The Comparator subtraction antipattern — returning a - b as a Comparator — can cause incorrect ordering due to integer overflow when a and b have opposite signs and their difference overflows int range. Always use Integer.compare(a, b) or Comparator.comparingInt() rather than subtraction for numeric comparisons.

Java

// ── Natural ordering — min-heap by default ───────────────────────────
PriorityQueue<String> strings = new PriorityQueue<>();
strings.offer("banana");
strings.offer("apple");
strings.offer("cherry");
System.out.println(strings.poll());  // "apple" — lexicographically smallest

// ── Max-heap using reverseOrder ───────────────────────────────────────
PriorityQueue<Integer> maxHeap =
    new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(4);
maxHeap.offer(1);
maxHeap.offer(5);
System.out.println(maxHeap.poll());   // 5 — largest value at head

// ── Custom ordering for domain objects ───────────────────────────────
record Task(String name, int priority, Instant submitted) {}

// Higher priority number = more urgent (reverse int order)
// Tie-break: earlier submission first (natural Instant order)
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed()
              .thenComparing(Task::submitted));

taskQueue.offer(new Task("low-task",    1, Instant.now()));
taskQueue.offer(new Task("high-task",   9, Instant.now().plusSeconds(1)));
taskQueue.offer(new Task("urgent-task", 9, Instant.now().minusSeconds(1)));

System.out.println(taskQueue.poll().name());  // "urgent-task" — priority 9, earlier
System.out.println(taskQueue.poll().name());  // "high-task"   — priority 9, later
System.out.println(taskQueue.poll().name());  // "low-task"    — priority 1

// ── DANGER: subtraction antipattern ──────────────────────────────────
// WRONG — overflows near Integer.MIN_VALUE / Integer.MAX_VALUE:
PriorityQueue<Integer> danger =
    new PriorityQueue<>((a, b) -> a - b);   // DO NOT DO THIS

// CORRECT — type-safe comparison:
PriorityQueue<Integer> safe =
    new PriorityQueue<>(Integer::compare);

// CORRECT — factory method:
PriorityQueue<Integer> safe2 =
    new PriorityQueue<>(Comparator.comparingInt(Integer::intValue));

// ── Initial capacity hint ─────────────────────────────────────────────
// PriorityQueue default capacity is 11
// If size is known, provide initial capacity to avoid resizing:
PriorityQueue<Integer> sized = new PriorityQueue<>(10_000);
// Avoids reallocation cost during bulk insertion

Algorithmic Applications

PriorityQueue is the enabling data structure for several fundamental algorithms. Dijkstra's shortest path algorithm uses a min-heap keyed by tentative distance: start with the source node at distance 0, repeatedly extract the nearest unvisited node and relax its edges, adding improved distances back to the heap. The min-heap ensures the closest unvisited node is always processed next, which is the greedy choice that makes Dijkstra's correct. Huffman coding builds an optimal prefix-free code by repeatedly merging the two lowest-frequency symbols. A min-heap keyed by frequency enables efficient extraction of the two minimum-frequency nodes at each step. Heap sort uses a binary heap (PriorityQueue equivalent) to sort in O(n log n) time with O(1) auxiliary space. The k-way merge problem — merging k sorted sequences — uses a min-heap that holds one element from each sequence; each poll gives the global minimum, which is then replaced by the next element from the same sequence. The sliding window maximum problem illustrates a subtle use: maintaining the maximum (or minimum) element of a sliding window over an array. A max-heap gives the current maximum, and elements that have left the window are removed lazily (only if they are the current head when peeked). This gives O(n log k) time for a window of size k. The k smallest or k largest elements problem uses a bounded heap of size k: for k smallest, maintain a max-heap of size k; for each new element, add it and remove the maximum if size exceeds k. The heap always contains the k smallest elements seen so far. This is O(n log k), which is faster than full sorting when k << n.

Java

// ── Dijkstra's shortest path ─────────────────────────────────────────
public Map<Integer, Integer> dijkstra(
        Map<Integer, List<int[]>> graph, int source) {

    Map<Integer, Integer> dist = new HashMap<>();
    // PriorityQueue of [distance, node] — min-heap by distance
    PriorityQueue<int[]> pq =
        new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));

    pq.offer(new int[]{0, source});
    dist.put(source, 0);

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int   d    = curr[0];
        int   node = curr[1];

        if (d > dist.getOrDefault(node, Integer.MAX_VALUE)) continue;

        for (int[] edge : graph.getOrDefault(node, List.of())) {
            int neighbour = edge[0];
            int newDist   = d + edge[1];
            if (newDist < dist.getOrDefault(neighbour, Integer.MAX_VALUE)) {
                dist.put(neighbour, newDist);
                pq.offer(new int[]{newDist, neighbour});
            }
        }
    }
    return dist;
}

// ── K smallest elements (max-heap of size k) ──────────────────────────
public int[] kSmallest(int[] nums, int k) {
    // Max-heap of size k: always contains the k smallest elements seen
    PriorityQueue<Integer> maxHeap =
        new PriorityQueue<>(k, Comparator.reverseOrder());

    for (int num : nums) {
        maxHeap.offer(num);
        if (maxHeap.size() > k) {
            maxHeap.poll();   // remove largest — keep only k smallest
        }
    }

    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        result[i] = maxHeap.poll();   // drain in ascending order
    }
    return result;
}

// ── K-way merge of sorted lists ───────────────────────────────────────
public List<Integer> kWayMerge(List<List<Integer>> sortedLists) {
    // [value, listIndex, elementIndex]
    PriorityQueue<int[]> pq =
        new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));

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

    List<Integer> result = new ArrayList<>();
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        result.add(curr[0]);
        int listIdx = curr[1];
        int elemIdx = curr[2] + 1;
        if (elemIdx < sortedLists.get(listIdx).size()) {
            pq.offer(new int[]{
                sortedLists.get(listIdx).get(elemIdx),
                listIdx,
                elemIdx
            });
        }
    }
    return result;
}

PriorityQueue Limitations and Thread Safety

PriorityQueue has several limitations that affect its use in production code. It is not thread-safe — concurrent access from multiple threads without external synchronisation will corrupt the heap invariant. For concurrent priority-based processing, PriorityBlockingQueue from java.util.concurrent is the correct choice. PriorityBlockingQueue is an unbounded thread-safe priority queue that blocks on take() when empty (but never blocks on put() because it is unbounded). PriorityQueue does not support efficient update of an element's priority. If an element's priority changes after insertion — for example, in Dijkstra's where a shorter path is found to a previously visited node — the standard approach is to insert the element again with the new priority rather than updating it in place. The old entry is left in the heap and discarded when polled (by checking whether the polled distance is greater than the recorded shortest distance). This lazy deletion approach is simple and correct, though it means the heap may contain stale entries. For applications requiring fast update and deletion of arbitrary elements, alternative priority queue implementations such as Fibonacci heaps provide O(1) amortised decrease-key operations. Java does not provide a Fibonacci heap in the standard library, and implementing one correctly is non-trivial. For most practical Dijkstra implementations where the graph has sparse edges (E ≈ V log V), the simple approach with re-insertion is efficient enough.

Java

// ── Thread-safe priority queue ────────────────────────────────────────
// PriorityBlockingQueue — thread-safe, unbounded, blocking on take()
PriorityBlockingQueue<Task> safeQueue =
    new PriorityBlockingQueue<>(11,
        Comparator.comparingInt(Task::priority).reversed());

// Producer thread — never blocks (unbounded)
executor.submit(() -> {
    safeQueue.offer(new Task("task1", 5));
    safeQueue.offer(new Task("urgent", 9));
});

// Consumer thread — blocks if empty
executor.submit(() -> {
    try {
        while (true) {
            Task task = safeQueue.take();   // blocks if empty
            process(task);
        }
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
});

// ── Lazy deletion for priority update ────────────────────────────────
// Dijkstra with re-insertion instead of decrease-key:
Set<Integer> processed = new HashSet<>();

while (!pq.isEmpty()) {
    int[] curr = pq.poll();
    int dist = curr[0], node = curr[1];

    // Skip stale entries — this node was already processed with a shorter dist
    if (!processed.add(node)) continue;  // add returns false if already present

    for (int[] edge : graph.getOrDefault(node, List.of())) {
        int newDist = dist + edge[1];
        if (newDist < distances.getOrDefault(edge[0], Integer.MAX_VALUE)) {
            distances.put(edge[0], newDist);
            pq.offer(new int[]{newDist, edge[0]});  // re-insert with new priority
            // old entry for edge[0] is still in heap but will be skipped
        }
    }
}

// ── Draining to sorted list ───────────────────────────────────────────
PriorityQueue<Integer> pq2 = new PriorityQueue<>(
    List.of(5, 2, 8, 1, 9, 3));

// Sorted in priority order:
List<Integer> sorted = new ArrayList<>();
while (!pq2.isEmpty()) sorted.add(pq2.poll());
// sorted: [1, 2, 3, 5, 8, 9]

// Alternative — Collections.sort is faster for one-time sorting:
// If you just want sorted output, Arrays.sort is O(n log n) with better constants

PriorityQueue

Binary Heap Internals and Performance

Natural Ordering and Custom Comparators

Algorithmic Applications

PriorityQueue Limitations and Thread Safety

Related Topics in Collections Framework