Heaps and Ordered Structures

How much order do you need?

Three servers are available. Each has a weight and an id. Requests arrive one per second, and each request occupies its assigned server for a known duration. An available server with lower weight wins; equal weights are settled by lower id. If every server is busy, the oldest waiting request is assigned as soon as a server becomes free.

There are two changing questions:

• Which busy server becomes available next?
• Which available server should receive the next request?

Sorting all servers for every request would answer both questions, but it would repeatedly compute order that no decision uses. The next finish matters; the complete order of later finishes does not. The best free server matters; the relative order of all the other free servers does not yet matter.

A heap is built for that limited knowledge. It keeps one extreme—the minimum or maximum—available while insertions and removals change the candidates. The discipline is to ask how much order the algorithm needs, then buy no more.

A heap knows the winner, not the standings

In a min-heap, each parent is no greater than its children. That local rule is enough to make the root a global minimum. It says almost nothing about the order elsewhere: a child in the left subtree need not precede a value in the right subtree, and the heap’s array representation is not sorted output.

Reading the root costs O(1). Inserting an entry or removing the root repairs a single root-to-leaf path and costs O(log n). An array of known items can be heapified in O(n). Arbitrary search and deletion are not native strengths: an item buried in the heap may be almost anywhere.

Those properties already suggest a contract for the server problem. Maintain two min-heaps:

• busy, keyed by (finish_time, weight, id), exposes the next release;
• available, keyed by (weight, id), exposes the next assignment.

Before assigning a request at time t, move every entry in busy whose finish time is at most t into available. If available is empty, advance t to the earliest finish and release every server finishing then. Only after that does the available root identify the winner.

time = 0
available = all servers keyed by (weight, id)
busy = empty heap keyed by (finish_time, weight, id)

for request_index, duration in requests:
    time = max(time, request_index)

    while busy and busy.min.finish_time <= time:
        move busy.pop_min() to available

    if available is empty:
        time = busy.min.finish_time
        while busy and busy.min.finish_time <= time:
            move busy.pop_min() to available

    weight, id = available.pop_min()
    assign request_index to id
    busy.push((time + duration, weight, id))

Take servers (weight=3, id=0), (1, 1), and (1, 2), with request durations [5, 4, 3, 2, 1]. Requests at times 0, 1, and 2 choose servers 1, 2, and 0. All three then finish at time 5. The request arriving at time 3 cannot be assigned immediately, so time jumps to 5. All three releases must be processed before choosing again; the (weight, id) rule selects server 1. The request that arrived at time 4 is considered next, also at time 5, and selects server 2.

The trace exposes details that a slogan such as “use two heaps” conceals. Time may move past several request arrivals. Releases at the same instant form one state change. The key fields encode policy, including the id tie-break. Most important, the heaps have different meanings even though both are min-heaps.

The invariant before each assignment is:

available contains exactly the free servers; busy contains every occupied server with its next release time; after all releases through time are processed, the root of available is the required server.

That statement supplies the correctness argument. No busy server is eligible. Every eligible server is in available. Heap order makes its root the least (weight, id) pair. Each request and each release causes a constant number of heap operations, so r requests on s servers take O(r log s) time and O(s) heap space.

The root can mean “worst item worth keeping”

Now change the question from “what acts next?” to “which of the best k items should be evicted?” For the k largest values seen in a stream, keep a min-heap whose size never exceeds k:

kept = empty min-heap

for value in stream:
    kept.push(value)
    if kept.size > k:
        kept.pop_min()

After any prefix of the stream, kept contains the largest min(k, prefix length) values in that prefix. When a new value arrives, temporarily keeping it gives k + 1 candidates; removing the smallest leaves exactly the best k. The root is therefore the worst retained item, and after the final value it is the kth largest.

That reversal of meaning is a common source of mistakes. A min-heap may expose the next item to process, as it did for server assignment, or the item to evict from a retained set. Name the root’s role before writing the push and pop.

Heap contents are not sorted. If the output requires the top k in descending order, sort the retained items at the end. If all input is already present and n log n is acceptable, sorting the whole batch may be the clearer solution. If only the kth value matters, quickselect offers expected O(n) time by partitioning, at the cost of mutation and a more delicate worst case. When priorities are small bounded integers—frequencies no larger than n, for example—buckets may make the logarithm and comparator unnecessary.

The same retained-boundary argument handles k closest points or the most frequent values. Store enough of the original item to return the answer, and define ties if the result must be deterministic. For the k smallest items, mirror the structure with a max-heap: its root is the largest retained value, the next eviction candidate.

A median needs two exposed boundaries

One heap cannot reveal the middle because the middle is not an extreme. Two heaps can maintain a partition:

• low is a max-heap containing the lower half;
• high is a min-heap containing the upper half;
• every item in low is no greater than every item in high;
• low has either the same number of valid items as high or one more.

Insertion follows the boundary, then restores the size rule:

if low is empty or value <= low.max:
    low.push(value)
else:
    high.push(value)

if low.size > high.size + 1:
    high.push(low.pop_max())
else if high.size > low.size:
    low.push(high.pop_min())

With an odd count, low.max is the median. With an even count, the result is derived from low.max and high.min; the prompt must say whether that means a floating average, lower median, or upper median. Each insertion costs O(log n), and the median remains O(1) to read.

This design is elegant for an insert-only stream. Expiration changes the operation mix. A sliding-window median must remove an old value that may be buried inside either heap. A balanced multiset supports ordered insertion, deletion, and access around the middle more directly. In a language without one, two heaps with lazy deletion can work, but the bookkeeping is no longer a minor detail.

Stale entries are debt, not disappearance

Lazy deletion leaves an obsolete heap entry in place until it reaches the root. Give every logical item a stable id or version, record the current version separately, and clean before every operation that relies on the root:

clean(heap):
    while heap is not empty:
        priority, id, version = heap.peek()
        if current[id] still matches (priority, version):
            return
        heap.pop()

Pushing a new version is safe only if old versions can be recognized. Peeking without cleaning can return a stale answer. Rebalancing two median heaps by their physical array lengths can also be wrong because those lengths include expired entries; maintain logical valid sizes instead.

Lazy deletion preserves asymptotic convenience, but it can retain many stale objects. For a long-running system, heavy churn, range queries, predecessor or successor lookup, or frequent arbitrary deletion, an indexed heap or balanced ordered structure may be the honest choice. The API should match the work, not the data-structure name one hoped to use.

One candidate per source is enough

Suppose k sorted streams must be merged. Sorting all their items again would discard information already present in the inputs. The next global value must be one of the current stream heads, so keep exactly those heads in a min-heap:

push the first item from each nonempty source,
keyed by (value, source_id, position)

while heap is not empty:
    value, source_id, position = heap.pop_min()
    output value
    if that source has another item:
        push its next item

The invariant is that the heap contains one current candidate from every source that still has data. Each source is already sorted, so nothing behind a head can precede that head. The least head is therefore the next global item. After it leaves, only its source can reveal a new candidate.

For N total items, the merge costs O(N log k) time and O(k) auxiliary heap space. A source_id or sequence number also prevents equal values from forcing the runtime to compare payload objects that have no natural order. When the sources are linked lists, the output may reuse nodes, but node identity and mutation then belong in the function’s contract.

K-way merge is one instance of a frontier: retain the best currently reachable candidate from each source, partition, or search region. A shortest-path algorithm with nonnegative edge weights uses a related priority frontier, although its entries may become stale when a cheaper route is discovered. The queue from an unweighted search stops being sufficient because discovery order no longer guarantees cheapest cost.

Priority is policy made executable

A heap compares keys, not intentions. Write the key in the exact order the policy applies:

(primary_priority, secondary_priority, stable_identity, payload)

An available server used (weight, id). A shortest task might use (processing_time, original_index). An event queue may need (time, event_kind, id) so releases occur before assignments at the same timestamp. For a max-heap implemented with a min-heap, negating a numeric priority is fine, but keep the convention local; a negative priority escaping into output or mixing with an unnegated field is an easy bug.

Do not mutate a priority field after insertion and expect the heap to repair itself. Push a new version and invalidate the old entry, or use a structure with an explicit update operation. Do not let the runtime fall through to comparing mutable payloads. Equal primary priorities are where an omitted policy becomes visible.

Priority simulations also need a progress rule. At each iteration, either an eligible item acts, an event changes eligibility, or time advances to the next event. A loop that repeatedly checks an empty eligible heap without moving time has a data structure but no algorithm.

Spend the smallest order budget that proves the result

A heap is a strong default when insertions and removals change the candidates and the algorithm repeatedly needs one extreme. A fixed-size heap is useful when only the best k must survive. Two heaps expose a moving partition such as a median. These are all forms of partial order.

Use a balanced tree, ordered multiset, or sorted map when the repeated work is predecessor or successor search, a range query, ordered iteration, or deletion of an arbitrary known key. The root of a heap cannot answer “what is the nearest value below this one?” without searching broadly.

Use sorting when one complete order lets the rest of the problem become a scan, when sorted output is required, or when the input is a fixed batch and O(n log n) is comfortably within the constraints. Use quickselect when one rank matters and its expected-time and mutation trade-offs are worthwhile. Use buckets when the priority domain is small enough that direct indexing is the simpler order.

Meeting rooms make the boundary between choices concrete. If meetings are processed by start time and the question is how many rooms are active, a min-heap of end times maintains changing releases. If the question is the maximum number of non-overlapping meetings one person can attend, sorting by end time and scanning is enough; no changing priority set is needed. The noun “scheduling” does not choose the structure. The repeated operation does.

Practice by changing the operation

Begin with kth largest in a stream. State why the root of a size-k min-heap is the answer. Then require descending output and add only the final ordering the new contract needs. Finally, make the input a fixed mutable array and solve for the kth value with quickselect. Compare the proof obligations, not just the runtime expressions.

Implement the insert-only median. Then turn it into a sliding-window median. Before coding the variation, write down which operation has appeared and why the original two-heap interface cannot perform it directly. Choose an ordered multiset or design lazy deletion with stable ids, logical sizes, and cleanup before every root read.

Merge sorted arrays, then sorted linked lists with duplicate values. Make the tie-break explicit and decide whether the lists may be mutated. Next, imagine that each source is a network stream whose next item arrives asynchronously. Identify which parts of the one-head-per-source proof survive and what new availability state the system needs.

Return to server assignment and change one policy at a time: higher weight wins, a server needs a cooldown after finishing, or waiting requests have their own priority. For each variation, write the meaning of both heap roots and the event that moves an item between states before changing the key.

The transferable skill is not recognizing a heap-shaped prompt. It is naming the boundary that must remain exposed while the candidates change. Once that boundary is precise, the structure, its invariant, and its failure cases tend to arrive together.

Related reading

• Chapter 31: Complexity and Constraint Analysis
• Chapter 33: Correctness Before Cleverness
• Chapter 41: Linked Structures, Stacks, Queues, and Deques
• Chapter 43: Sorting, Searching, and Intervals