Heap Patterns Explained | Backend Study Lab

Quick answer

A heap is useful when an algorithm repeatedly needs the smallest, largest, earliest, cheapest, or otherwise best candidate while values are added or removed. A Java PriorityQueue exposes the heap’s head in constant time and inserts or removes the head in O(log n).

The key pattern is to keep only the frontier the answer needs. A min-heap keeps the next smallest candidate; a size-k min-heap can retain the largest k values; two heaps split a stream around its median; a k-way merge heap tracks one candidate from each sorted source.

Recognition signals

Consider a heap when the problem says:

find the top or bottom k;
find the kth largest or smallest;
repeatedly choose the next minimum/maximum;
merge several sorted streams;
process jobs by deadline or priority;
maintain a streaming median;
explore the cheapest known state next;
keep only the best candidates seen so far.

If the problem needs a fully sorted result once, sorting may be simpler. If it needs arbitrary membership or lookup by key, a hash map may be primary. If priorities change frequently for existing items, Java PriorityQueue has no efficient decrease-key operation; duplicate entries with stale-state checks or an indexed heap may be necessary.

Java PriorityQueue behavior

Java’s PriorityQueue is a min-heap according to natural order or a supplied Comparator. peek() returns the least element and poll() removes it. Ties at the head are broken arbitrarily, and iteration is not sorted.

PriorityQueue<Integer> minimums = new PriorityQueue<>();
PriorityQueue<Integer> maximums =
    new PriorityQueue<>(Comparator.reverseOrder());

Do not print or iterate a priority queue and expect priority order. Repeatedly polling a copy produces ordered output but costs O(n log n).

Pattern 1: largest K with a bounded min-heap

To keep the largest k values seen so far, maintain a min-heap of size at most k. The head is the weakest retained candidate:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

static List<Integer> largestK(int[] values, int k) {
    if (values == null) {
        throw new IllegalArgumentException("values must not be null");
    }
    if (k < 0 || k > values.length) {
        throw new IllegalArgumentException("k must be between 0 and n");
    }
    if (k == 0) return List.of();

    PriorityQueue<Integer> best = new PriorityQueue<>();
    for (int value : values) {
        if (best.size() < k) {
            best.offer(value);
        } else if (value > best.peek()) {
            best.poll();
            best.offer(value);
        }
    }

    List<Integer> result = new ArrayList<>(best);
    result.sort(Comparator.reverseOrder());
    return List.copyOf(result);
}

Each of n items does at most one O(log k) replacement, so selection is O(n log k). Sorting the k outputs costs O(k log k). Space is O(k).

For the smallest k, reverse the structure: keep a size-k max-heap so its head is the largest retained candidate.

Pattern 2: kth largest

The same bounded min-heap returns the kth largest at its head after scanning:

static int kthLargest(int[] values, int k) {
    if (values == null || k < 1 || k > values.length) {
        throw new IllegalArgumentException("k must be in [1,n]");
    }
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int value : values) {
        heap.offer(value);
        if (heap.size() > k) heap.poll();
    }
    return heap.peek();
}

Quickselect has expected linear time and may be better for one in-memory query, while a heap is straightforward, supports streaming input, and has predictable O(n log k) time.

Why the heap direction feels reversed

To retain the largest values, use a min-heap. You need fast access to the smallest of the winners—the candidate to evict when something better arrives.

Ask:

Which retained item becomes irrelevant first?

Put that item at the head. This question is more reliable than memorizing “top K means min-heap.”

Pattern 3: streaming median with two heaps

Split values into:

a max-heap lower containing the lower half;
a min-heap upper containing the upper half.

Maintain size difference at most one and every lower value <= every upper value:

final class MedianTracker {
    private final PriorityQueue<Integer> lower =
        new PriorityQueue<>(Comparator.reverseOrder());
    private final PriorityQueue<Integer> upper =
        new PriorityQueue<>();

    void add(int value) {
        if (lower.isEmpty() || value <= lower.peek()) {
            lower.offer(value);
        } else {
            upper.offer(value);
        }
        if (lower.size() > upper.size() + 1) {
            upper.offer(lower.poll());
        } else if (upper.size() > lower.size()) {
            lower.offer(upper.poll());
        }
    }

    double median() {
        int size = lower.size() + upper.size();
        if (size == 0) {
            throw new IllegalStateException("no values");
        }
        if (lower.size() == upper.size()) {
            return ((long) lower.peek() + upper.peek()) / 2.0;
        }
        return lower.peek();
    }
}

The long cast prevents overflow when averaging two extreme integers. Insertion is O(log n) and median lookup is O(1).

Removing arbitrary old values for a sliding-window median is harder because PriorityQueue.remove(Object) is linear. Delayed deletion maps or balanced trees are common alternatives.

Pattern 4: k-way merge

When k lists are individually sorted, place only the first element from each list in a min-heap. Poll the smallest, append it, and add the next element from the same list:

record Cursor(int value, int listIndex, int elementIndex) {}

static List<Integer> mergeSorted(List<List<Integer>> lists) {
    PriorityQueue<Cursor> heap = new PriorityQueue<>(
        Comparator.comparingInt(Cursor::value)
            .thenComparingInt(Cursor::listIndex)
            .thenComparingInt(Cursor::elementIndex)
    );

    for (int listIndex = 0; listIndex < lists.size(); listIndex++) {
        if (!lists.get(listIndex).isEmpty()) {
            heap.offer(new Cursor(
                lists.get(listIndex).get(0), listIndex, 0
            ));
        }
    }

    List<Integer> result = new ArrayList<>();
    while (!heap.isEmpty()) {
        Cursor current = heap.poll();
        result.add(current.value());
        int nextIndex = current.elementIndex() + 1;
        List<Integer> source = lists.get(current.listIndex());
        if (nextIndex < source.size()) {
            heap.offer(new Cursor(
                source.get(nextIndex),
                current.listIndex(),
                nextIndex
            ));
        }
    }
    return List.copyOf(result);
}

For N total elements and at most k heap entries, time is O(N log k) and frontier space is O(k), excluding output.

Pattern 5: scheduling

Scheduling problems vary:

earliest finishing job: min-heap by end time;
highest priority job: comparator by priority, then stable tie-breaker;
meeting rooms: sort starts and keep active end times in a min-heap;
CPU simulation: add newly available jobs, then poll the next eligible priority.

The heap contains eligible work, not necessarily all work. Many simulations first sort by release time and advance a pointer that feeds the heap.

Use deterministic tie-breakers:

record Job(long readyAt, int priority, long sequence) {}

Comparator<Job> order =
    Comparator.comparingInt(Job::priority).reversed()
        .thenComparingLong(Job::readyAt)
        .thenComparingLong(Job::sequence);

Avoid b.priority() - a.priority(): subtraction can overflow.

Pattern 6: best-first search

Dijkstra’s algorithm and A* use a priority frontier. Java’s queue cannot efficiently update an existing entry, so a common approach adds a new record when a better cost is found and ignores stale records when polled:

record State(String vertex, long cost) {}

State current = heap.poll();
if (current.cost() != bestCost.get(current.vertex())) {
    continue; // stale entry
}

This works because the authoritative best-cost map decides whether an entry is current. Do not use this pattern without the stale check; obsolete work can produce incorrect processing or excessive cost.

Heap construction versus repeated insertion

Constructing a PriorityQueue from a collection can heapify more efficiently than inserting one by one, though API guarantees should be checked for the required complexity. For a bounded top-K heap, one-by-one streaming is inherent.

If you need every item in sorted order, Arrays.sort or List.sort communicates the goal more clearly. A heap shines when only a prefix or dynamic frontier is needed.

Mutable elements are dangerous

A heap assumes the comparator result for stored elements stays consistent. If code changes a job’s priority after insertion, the queue does not automatically reposition it.

Prefer immutable records. To change priority, remove/reinsert if cost is acceptable, or insert a new version and discard stale versions using an ID-to-version map.

Also avoid comparators based on external mutable state. The heap invariant can silently become invalid.

Duplicates and ties

Heaps allow duplicates. Decide whether top K counts repeated values or distinct values. For distinct values, combine a set with the heap or preprocess uniqueness.

Java does not guarantee which tied head appears first. If stable order matters, include a sequence number in the comparator. Ensure that two distinct items do not compare equal unless arbitrary tie order is acceptable.

Complexity table

Pattern	Heap size	Time
Largest or smallest K	`k`	`O(n log k)`
Kth element	`k`	`O(n log k)`
Streaming median	`n` across two heaps	`O(log n)` per add
K-way merge	at most `k`	`O(N log k)`
Poll every value in order	up to `n`	`O(n log n)`

peek is O(1); offer and poll are O(log n) in Java’s implementation. contains and remove(Object) are linear, which rules out some naive update/delete designs.

Testing Java heap patterns

@Test
void largestKHandlesDuplicatesAndNegativeValues() {
    assertEquals(
        List.of(9, 9, 4),
        largestK(new int[] {4, -1, 9, 2, 9}, 3)
    );
}

@Test
void validatesKBoundaries() {
    assertEquals(List.of(), largestK(new int[] {1, 2}, 0));
    assertThrows(
        IllegalArgumentException.class,
        () -> largestK(new int[] {1, 2}, 3)
    );
}

@Test
void medianAvoidsIntegerOverflow() {
    MedianTracker tracker = new MedianTracker();
    tracker.add(Integer.MAX_VALUE);
    tracker.add(Integer.MAX_VALUE);
    assertEquals((double) Integer.MAX_VALUE, tracker.median());
}

For k-way merge, test empty source lists, duplicates, one list, all empty lists, negative values, and deterministic ties.

Common mistakes

The first mistake is choosing heap direction from the requested word rather than the eviction candidate.

The second is assuming iteration is sorted.

The third is using subtraction in a comparator.

The fourth is mutating priorities after insertion.

The fifth is using linear remove(Object) inside a performance-critical update path.

The sixth is keeping all n values for a top-K problem when O(k) space is sufficient.

The seventh is failing to define duplicate and tie behavior.

The eighth is using a heap when a one-time full sort is simpler and equally efficient for the required output.

Practical checklist

Identify the repeatedly needed best candidate.
Put the easiest retained candidate to evict at the head.
Bound heap size when only K winners matter.
Validate k, empty input, and duplicate policy.
Use immutable heap elements.
Use comparator factories or compare methods, not subtraction.
Add deterministic tie-breakers when output order matters.
Never assume iterator order.
Account for linear contains and arbitrary removal.
Use stale-entry checks for best-first updates.
Cast before arithmetic that can overflow.
Compare heap complexity with sorting or quickselect.
Continue through the Algorithms learning path and topic clusters.

Frequently asked questions

Is Java PriorityQueue a min-heap?

Its head is the least element under natural order or the supplied comparator. A reversed comparator gives max-heap behavior.

Why use a min-heap for the largest K?

The smallest winner is the one to evict when a better value arrives, so it belongs at the head.

Is PriorityQueue iteration sorted?

No. Poll a copy or sort an array/list when ordered traversal is required.

When is sorting better?

When every item must be returned in order once, sorting is usually simpler. Heaps excel at partial, streaming, or dynamic selection.

Can I update an item’s priority?

Not in place safely. Reinsert a new immutable version with stale detection, or use a data structure designed for indexed priority updates.

Sources and further reading

Oracle, PriorityQueue in Java SE 25.
Oracle, Comparator in Java SE 25.
Princeton Algorithms, Priority Queues.

Read Java PriorityQueue Explained for API fundamentals, Top K Elements Explained for focused interview examples, and Merge Intervals Explained for scheduling boundaries. Continue through the Algorithms learning path and topic clusters.