Heap

What it is

A heap maintains a collection so that its highest-priority element is cheap to retrieve. A min-heap exposes the smallest key; a max-heap exposes the largest. A heap is not a fully sorted collection: only the root is guaranteed to be the next element in priority order.

A binary heap is a complete binary tree, usually stored in an array. In a min-heap, every parent is no greater than its children. For index i, the children are at 2*i + 1 and 2*i + 2.

Insertion moves a new element upward until the heap property holds. Removing the root replaces it with the last element, then moves that element downward. Both operations follow a tree path of length O(log n).

The advantage appears when priorities change or elements arrive incrementally. Repeatedly scanning an unsorted collection for its minimum costs O(n) per selection. A heap provides O(1) access to the minimum and O(log n) removal, without maintaining a complete ordering.

Python's heapq implements a min-heap. Negating a numeric priority gives max-heap behavior. heapify builds a heap from an existing list in linear time.

How to recognize it

Look for these signals:

• Repeatedly choose the smallest, largest, earliest, or highest-priority available item.
• Remove a selected item, change its priority, and return it to the collection.
• Keep only the best k items from a stream or large input.
• Combine sorted streams while examining only their current frontiers.
• Repeatedly combine the two smallest current weights.
• Maintain the best candidate while updates or expiration invalidate old entries.
• Process candidates in one order, but select among them in another order.

A heap is less attractive when the input is static and a single sort solves the task. It also does not directly support arbitrary range queries, fast membership tests, or efficient search for a particular item.

The core technique

1. Priority queues and changing priorities

Define the priority key before writing the algorithm. Include every required tie-breaker. Python compares tuples lexicographically, so (load, index) selects minimum load, then minimum index.

import heapq

loads = [(0, i) for i in range(resource_count)]
heapq.heapify(loads)

for duration in durations:
    load, index = heapq.heappop(loads)
    assign(index, duration)
    heapq.heappush(loads, (load + duration, index))

This pattern applies when the selected resource's priority changes after each assignment. The invariant is that the heap contains exactly one current entry per resource.

For maximum score with smaller-index tie-breaking, use (-score, index). Negate only the score: negating the index would reverse the tie rule. After selecting an item, compute its new score and push its new key.

When priorities change for arbitrary items, locating and editing their heap entries is awkward. Use lazy invalidation:

• Keep each item's current value and version in a dictionary.
• On an update, increment its version and push a new entry.
• Before using the root, discard entries whose versions no longer match.

Versions distinguish stale entries even when a priority changes back to an earlier value. The heap may contain historical entries, but the first valid root represents the current answer.

Expiration uses the same idea. Discard expired roots before selecting an item. With release times, first insert all items released by the current time. If none remain eligible, jump to the next release. For nonpreemptive service, eligibility is checked when service starts; later arrivals do not interrupt it. Whether equality at a deadline is valid depends on the stated rule.

2. Bounded heaps for top-k selection

To retain the k largest values, maintain a min-heap of at most k entries. Its root is the weakest retained candidate, so it defines the admission threshold.

import heapq

def largest_k(values, k):
    if k <= 0:
        return []
    heap = []
    for value in values:
        if len(heap) < k:
            heapq.heappush(heap, value)
        elif value > heap[0]:
            heapq.heapreplace(heap, value)
    return sorted(heap, reverse=True)

For the k smallest values, use a max-heap instead. If candidates have identities or tie rules, store a composite key whose minimum means “worst retained.” The heap itself does not return the retained candidates in sorted order.

3. Multiway merging and frontier advancement

When several inputs are sorted, keep one current item from each input in a min-heap. Pop the smallest, then replace it with the next item from the same input.

import heapq

def merge_sorted(lists):
    heap = [(a[0], i, 0) for i, a in enumerate(lists) if a]
    heapq.heapify(heap)
    while heap:
        value, i, j = heapq.heappop(heap)
        yield value
        j += 1
        if j < len(lists[i]):
            heapq.heappush(heap, (lists[i][j], i, j))

The invariant is that each active input contributes its smallest unconsumed item. This reduces selection from scanning every input to one heap operation.

A related range technique keeps one representative from every sorted input and tracks their maximum separately. The heap root is the current minimum. Evaluate the interval between minimum and maximum, then advance the input supplying the minimum. Advancing another input cannot raise the minimum and may increase the maximum. Stop when a required input is exhausted.

4. Greedy selection backed by a heap

A heap implements a greedy choice; it does not prove that choice correct.

For additive pairwise merge costs, repeatedly extract the two smallest weights, add their sum to the total cost, and reinsert that sum. Small weights should participate in more repeated combinations than large weights; an exchange argument establishes the greedy rule.

For maximum-value unit-time jobs with positive integer deadlines, sweep jobs by increasing deadline. Insert each value into a min-heap. If retained job count exceeds the current deadline, evict the lowest-value job. The heap retains the best feasible subset; deterministic ties require an appropriate eviction key.

For sequential progress with previously reachable supplies, defer choosing a supply until more capacity is necessary. Store available supplies in a max-heap and select the largest when progress becomes impossible. This retroactive choice minimizes additional selections under the model's reachability and additive-supply assumptions.

Common mistakes

• Treating heap storage as sorted. Only the root has guaranteed global priority.
• Changing an entry's key in place without restoring the heap property.
• Forgetting tie-breakers or allowing tuple comparison to reach non-comparable payloads.
• Using a min-heap when the algorithm needs maximum selection.
• Reading a lazy heap's root without first removing stale or expired entries.
• Assuming lazy invalidation uses space proportional only to active items. Historical entries accumulate.
• Calling heapreplace on an empty heap, or replacing the root before checking admission conditions.
• Assuming repeated best-looking choices are optimal without a greedy argument.

Complexity

For a binary heap containing h entries:

• Root inspection: O(1).
• Insertion, root removal, or replacement: O(log h).
• Building with heapify: O(h); most nodes are near the leaves and require little repair.
• Storage: O(h).

Top-k selection takes O(n log k) time and O(k) space, plus optional output sorting. Merging N items across m inputs takes O(N log m) time and O(m) auxiliary space.

Greedy algorithms with a constant number of heap operations per item typically take O(n log n) time. Lazy heaps are amortized over all inserted entries: each stale entry is removed at most once, but a single query may discard many entries, and memory reflects accumulated updates.