Using Heaps for Top-K Selection and Priority Scheduling

Welcome back. In the previous lesson, sorting let you maintain a single interval frontier: the finish time of the last selected activity, or the right edge of a merged interval. This lesson extends that idea to situations with many candidates or many active frontiers. A heap lets you repeatedly access the one boundary that matters most without sorting everything again.

You will learn to recognize two high-frequency interview patterns:

• Top-$k$: retain only the best $k$ candidates seen so far.
• Priority scheduling: repeatedly select the most urgent ready task, or track the earliest resource that becomes free.

The central skill is not merely knowing that a PriorityQueue exists. It is choosing a min-heap or max-heap deliberately, stating what the heap contains, and explaining its invariant and complexity.

Study time: about 40–45 minutes.

---

1. A heap is ordered enough, not fully sorted

A priority queue stores items along with an ordering rule and efficiently returns the item at the front of that rule.

Unlike a regular FIFO queue:

• A regular queue removes the earliest inserted item.
• A priority queue removes the item considered smallest or largest by its comparator.

A binary heap is the usual implementation. It is a complete binary tree stored compactly in an array. Its key property is local:

• In a min-heap, every parent is no greater than its children.
• In a max-heap, every parent is no smaller than its children.

That does not mean every element is globally sorted. Only the root is guaranteed to be the minimum or maximum, respectively.

For a heap holding $h$ items:

Operation	Cost	Why
Read best item with peek()	$O(1)$	The best item is at the root
Insert with offer()	$O(\log h)$	The item may swim up one tree height
Remove best item with poll()	$O(\log h)$	The replacement may sink down one tree height

The heap height is logarithmic because the tree is complete.

Java PriorityQueue essentials

Java’s PriorityQueue is a min-heap by default. Its peek() and poll() return the element considered smallest by its ordering.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

minHeap.offer(8);
minHeap.offer(3);
minHeap.offer(5);

int smallest = minHeap.peek();  // 3
int removed = minHeap.poll();   // 3

To treat the largest integer as the head, supply a reversed comparator:

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

maxHeap.offer(8);
maxHeap.offer(3);
maxHeap.offer(5);

int largest = maxHeap.peek();   // 8

Two interview-important cautions:

1. Do not expect iteration or printing to be sorted. A heap guarantees only that its head is best. If you print a PriorityQueue, its internal array order may look strange but still be valid.

2. Do not mutate priority fields while an object is in the heap. Java will not automatically reheapify when a task’s deadline or priority changes. Use immutable task objects, or remove and reinsert an updated task.

---

2. The top-$k$ rule: keep the boundary candidate at the root

For top-$k$ problems, the heap normally represents the items that are currently good enough to survive. The root is intentionally the weakest survivor, because that is the item you would discard next.

This yields a compact decision rule:

Goal	Heap to maintain	Root represents
$k$ largest values	Min-heap of size $k$	Smallest among retained large values
$k$ smallest values	Max-heap of size $k$	Largest among retained small values
$k$-th largest value	Min-heap of size $k$	The $k$-th largest value
$k$-th smallest value	Max-heap of size $k$	The $k$-th smallest value

Why use a min-heap for the $k$ largest values?

This often feels backwards at first. Suppose you need the three largest values in this input:

$$[8,3,12,5,10,2]$$

Maintain a min-heap with capacity $k=3$.

Value processed	Heap after enforcing size $3$	Interpretation
8	$[8]$	One candidate retained
3	$[3,8]$	Both retained
12	$[3,8,12]$	Heap is full
5	$[5,8,12]$	3 is discarded
10	$[8,10,12]$	5 is discarded
2	$[8,10,12]$	2 is immediately discarded

The final heap contains the three largest values. Its root, $8$, is the smallest of those retained values and therefore the third-largest item overall.

The algorithm is simple:

1. Add every candidate to a min-heap.
2. If the heap grows beyond $k$, remove its minimum.
3. After all candidates are processed, the heap holds the $k$ largest candidates.

The loop invariant is:

After processing any prefix of the input, the heap contains the $k$ largest elements of that prefix, or all processed elements if fewer than $k$ have appeared.

When a new value arrives, only one item must be discarded: the smallest among the retained candidates plus the new candidate. A min-heap exposes exactly that item at its root.

A max-heap would put the largest retained item at the root, which is not the item you need to evict when capacity is exceeded. You could still use a max-heap containing every item, but then you would use more memory and pay for a larger heap.

Complexity: heap versus sorting

For $n$ input values:

• Sorting all values costs:

$$O(n\log n)$$

• A bounded heap of size $k$ costs:

$$O(n\log k)$$

• It uses:

$$O(k)$$

auxiliary heap space.

The heap approach is especially valuable when $k$ is much smaller than $n$, or when values arrive continuously and you cannot repeatedly sort the whole history.

If the problem asks for all values in sorted order and $k$ is close to $n$, sorting may be simpler and equally appropriate. Data-structure choice should follow the query and constraints, not habit.

---

3. Top-$k$ frequent elements: count first, then filter

“Top $k$ frequent elements” has two distinct phases:

1. Count each value’s frequency with a hash map.
2. Keep only the $k$ entries with the highest counts using a bounded min-heap.

Let:

• $n$ be the input length.
• $m$ be the number of distinct values.

For example:

$$[1,1,1,2,2,3]$$

produces the frequency map:

$$\{1:3,2:2,3:1\}$$

For $k=2$, the heap retains entries for 1 and 2. When the entry for 3 is considered, it is the weakest frequency candidate and is removed.

Java implementation

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TopKFrequent {

    record Frequency(int value, int count) { }

    static int[] findTopKFrequent(int[] nums, int k) {
        if (k <= 0) {
            return new int[0];
        }

        Map<Integer, Integer> counts = new HashMap<>();

        for (int value : nums) {
            counts.merge(value, 1, Integer::sum);
        }

        PriorityQueue<Frequency> heap = new PriorityQueue<>(
            Comparator.comparingInt(Frequency::count)
                      .thenComparingInt(Frequency::value)
        );

        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            heap.offer(new Frequency(entry.getKey(), entry.getValue()));

            if (heap.size() > k) {
                heap.poll();
            }
        }

        int[] result = new int[heap.size()];

        // Polling gives lowest retained frequency first.
        // Fill from the end to return descending frequency order.
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = heap.poll().value();
        }

        return result;
    }
}

The heap comparator sorts by count ascending, so the root is the least frequent retained element. That is precisely the entry that should leave whenever more than $k$ candidates are present.

The complexity is:

$$O(n+m\log k)$$

• Counting all values costs $O(n)$.
• Each of the $m$ distinct map entries may be inserted and removed from a heap of size at most $k$, costing $O(\log k)$.
• The frequency map requires $O(m)$ space.
• The heap uses $O(k)$ space.

A concise interview explanation is:

“I first count frequencies in a hash map. Then I maintain a min-heap of at most $k$ entries ordered by frequency. The root is the least frequent retained candidate, so whenever the heap exceeds $k$, I remove it. The invariant is that the heap contains the $k$ highest-frequency entries seen so far. The total complexity is $O(n+m\log k)$, where $m$ is the number of distinct values.”

Ties are part of the specification

If several values share the same frequency, a prompt may accept any order. If it requires a deterministic result, define a tie-breaker explicitly, such as smaller numerical value first or lexicographically smaller identifier first.

That tie-breaker must be part of the comparator. It is not enough to rely on map iteration order, because HashMap does not promise a stable semantic ordering.

---

4. Streaming $k$-th largest: the same invariant, preserved over time

A streaming problem differs from a batch top-$k$ problem because values keep arriving. You cannot sort the entire input after every addition.

Maintain a min-heap of size at most $k$:

import java.util.PriorityQueue;

public class KthLargest {

    private final int k;
    private final PriorityQueue<Integer> largest;

    public KthLargest(int k, int[] initialValues) {
        this.k = k;
        this.largest = new PriorityQueue<>();

        for (int value : initialValues) {
            addInternal(value);
        }
    }

    public int add(int value) {
        addInternal(value);

        if (largest.size() < k) {
            throw new IllegalStateException(
                "Fewer than k values have been received"
            );
        }

        return largest.peek();
    }

    private void addInternal(int value) {
        largest.offer(value);

        if (largest.size() > k) {
            largest.poll();
        }
    }
}

After every completed add, assuming at least $k$ values have been seen:

$$\text{largest.peek()}$$

is the $k$-th largest value.

Each new value costs:

$$O(\log k)$$

The key reason discarded values never need to return is that this version of the stream only adds values. Once a value is smaller than $k$ retained values, later insertions cannot make it $k$-th largest again.

---

5. Priority scheduling: choose the next ready task

Top-$k$ problems use a bounded heap because you only need a limited set of candidates. A priority scheduler usually needs a different model: it keeps all currently ready tasks, because any ready task might need to run next.

Suppose a backend worker receives jobs with a numeric priority, where a larger number means more urgent. You want poll() to return the highest-priority job first.

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityScheduler {

    record Job(String id, int priority, long sequence) { }

    private final PriorityQueue<Job> readyJobs =
        new PriorityQueue<>(
            Comparator.comparingInt(Job::priority)
                      .reversed()
                      .thenComparingLong(Job::sequence)
        );

    public void submit(Job job) {
        readyJobs.offer(job);
    }

    public Job nextJob() {
        return readyJobs.poll();
    }

    public Job peekNextJob() {
        return readyJobs.peek();
    }
}

This comparator encodes two policies:

1. Larger priority values run first.
2. For equal priorities, the smaller sequence value runs first, giving deterministic FIFO behavior within a priority level.

Here, the heap invariant is:

readyJobs contains all submitted but not yet dispatched jobs, and its root is the job that should execute next under the scheduling policy.

If there are $r$ ready jobs:

• Submission costs $O(\log r)$.
• Selecting the next job costs $O(\log r)$.
• Inspecting the next job costs $O(1)$.

A priority queue chooses what should run next. It does not itself execute tasks, enforce concurrency limits, or make a system fair across tenants. Those are separate scheduler policies and runtime concerns. For an interview question, first identify whether the prompt asks you to select by explicit task priority, by deadline, by arrival order, or by resource availability.

---

6. Minimum meeting rooms: a min-heap of active end times

This pattern builds directly on the interval work from the previous lesson.

In activity selection, one room was available, so you tracked one lastFinish boundary.

In minimum meeting rooms, many meetings can overlap, so you must track the end times of all active meetings. The most useful one is the earliest ending meeting, because it is the first room that might become available.

That means:

• Sort meetings by start time.
• Maintain a min-heap of end times for active meetings.
• Before handling a new meeting, remove every meeting that has already ended.
• Add the new meeting’s end time.
• Track the largest heap size observed.

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

public class MeetingRooms {

    record Meeting(int start, int end) { }

    static int minimumRooms(List<Meeting> meetings) {
        if (meetings.isEmpty()) {
            return 0;
        }

        List<Meeting> sorted = new ArrayList<>(meetings);
        sorted.sort(Comparator.comparingInt(Meeting::start));

        PriorityQueue<Integer> activeEndTimes = new PriorityQueue<>();
        int maximumConcurrentMeetings = 0;

        for (Meeting meeting : sorted) {
            while (!activeEndTimes.isEmpty()
                    && activeEndTimes.peek() <= meeting.start()) {
                activeEndTimes.poll();
            }

            activeEndTimes.offer(meeting.end());

            maximumConcurrentMeetings = Math.max(
                maximumConcurrentMeetings,
                activeEndTimes.size()
            );
        }

        return maximumConcurrentMeetings;
    }
}

For these meetings:

$$[0,30],[5,10],[15,20]$$

the trace is:

Meeting	Active end times after processing	Rooms needed so far
$[0,30]$	$[30]$	1
$[5,10]$	$[10,30]$	2
$[15,20]$	$[20,30]$	2

At time 15, the meeting ending at time 10 has released a room. The meeting ending at time 30 is still active.

The invariant is:

Before adding the current meeting, the heap contains exactly the end times of earlier meetings that still overlap the current meeting’s start time. After adding the current meeting, heap size equals the number of rooms currently in use.

Because the heap root is the earliest ending active meeting, it is the only end time you need to examine to know whether at least one room is free.

The complexity is:

$$O(n\log n)$$

Sorting costs $O(n\log n)$, and each meeting end time enters and leaves the heap at most once.

Endpoint semantics still matter

The code uses:

activeEndTimes.peek() <= meeting.start()

This means a meeting ending at 10 and another starting at 10 may use the same room. If the domain says handoff time is required and shared endpoints conflict, use a strict comparison instead.

---

7. A reliable heap-selection workflow

When an interview prompt involves rankings, schedules, or repeated “best next” decisions, use this sequence:

1. Identify the query.
   Is it asking for the next best task, the best $k$ items, the $k$-th ranked item, or the earliest available resource?

2. Identify the eviction or decision boundary.
   For top-$k$ largest, the boundary is the smallest retained value. For meeting rooms, it is the earliest ending active meeting.

3. Put that boundary at the heap root.
   Use a min-heap when you must quickly remove or inspect the smallest boundary; use a max-heap when you must quickly remove or inspect the largest boundary.

4. State the invariant.
   Explain exactly what the heap contains after each processed item.

5. Give the heap-size-based complexity.
   A heap of size $k$ yields $O(\log k)$ updates. A scheduler containing $r$ ready jobs yields $O(\log r)$ updates.

A useful verbal template is:

“I use a heap because I repeatedly need the boundary element, not a fully sorted collection. The comparator puts that boundary at the root. After each iteration, the heap represents the valid candidates or active tasks under the stated invariant, so insertion and removal cost logarithmic time in the heap size.”

---

Key takeaways

• A binary heap is partially ordered: its root is optimal, but the whole structure is not sorted.
• For the $k$ largest items, use a min-heap of size $k$. Its root is the weakest retained candidate and is the correct item to evict.
• For the $k$ smallest items, reverse the idea: use a max-heap of size $k$.
• Top-$k$ frequent elements combines a hash-map counting pass with a bounded min-heap, giving:

$$O(n+m\log k)$$

where $m$ is the number of distinct values.

• For priority scheduling, configure the comparator so poll() returns the next task according to the actual business policy.
• For minimum meeting rooms, sort by start time and use a min-heap of active end times; the root is the earliest resource release.

Next, you will switch from ordering-based problems to graph traversal. You will learn how to choose breadth-first search or depth-first search based on whether the prompt requires shortest layers, reachability, component exploration, or structured backtracking.