Heaps

Use a heap when items arrive over time and each query needs the current smallest or largest item. If all values are known and processed once in order, compare against sorting first.

1. Choose the Heap by What Must Leave First

For a binary heap with n items, peek costs $O(1)$, push/pop $O(\log n)$, and bottom-up heapify $O(n)$. Storage is $O(n)$. The array is not sorted: only the root is guaranteed to be the extreme value.

For an array implementation, children of index i are 2*i+1 and 2*i+2; the parent is (i-1)//2. Insertion sifts up; removal replaces the root with the last item and sifts down. Bottom-up heapify starts at the last parent: most nodes are near the leaves, so total repair work is linear. Use library operations unless implementation is the task.

2. Keep Only the Best K Candidates

After each input value, retain the largest k values seen so far. Adding one value can create only one excess candidate; removing the smallest restores the invariant. Duplicates count as separate values.

import heapq

def largest_k(values, k):
    if k <= 0:
        return []
    kept = []
    for value in values:
        heapq.heappush(kept, value)
        if len(kept) > k:
            heapq.heappop(kept)
    return kept

The result is unordered. For 1 <= k <= n, the root is the kth largest; sorting the retained values adds $O(k\log k)$. Scanning takes $O(n\log(k+1))$ time and $O(k)$ space. Heapifying all values and popping k instead takes $O(n+k\log n)$ time and $O(n)$ storage. Quickselect is another option for a single batch query; it does not maintain an answer as new items arrive.

In Top K Frequent Elements, count first, then keep (frequency, value) candidates. With U unique values, the map costs $O(U)$ space even if the heap holds only k items.

3. Merge Sorted Streams and Track a Median

Multiway merge: for ascending lists, heapify (value, list_id, index) for each nonempty list's first item. Pop the smallest, emit it, and insert its successor from the same list. Each list's head is its smallest unseen value, so the smallest head is the next global value. With m lists and N total elements, full output takes $O(m+N\log(m+1))$ time and $O(m)$ auxiliary space. Stop after k outputs for $O(m+k\log(m+1))$ time. Empty lists contribute nothing.

Running median: keep the lower half in a max-heap low and the upper half in a min-heap high. Every value in low must be <= every value in high, and len(high) must equal len(low) or exceed it by one. Insert relative to high's root, then move a root across if the sizes violate that rule. For odd size, the median is high's root; for even size, average the two roots. Insertion costs $O(\log n)$, lookup $O(1)$, and storage $O(n)$. Define the empty-stream result before reading either root.

4. Changing Priorities and Deleted Items

A heap does not provide efficient arbitrary lookup. In Delete Operations, pair each value with its original index and track which indices remain active. Index deletion updates that state; minimum deletion first pops stale roots, then removes the smallest active one. Rebuild the final result by original index to preserve order.

For changing priorities, keep (priority, id, version) entries and a map of current versions. Push an updated entry and discard obsolete versions when they reach the root. Do not mutate a priority inside the heap without repairing it. Across q inserted entries, each stale entry is removed once, giving $O(q\log(q+1))$ total heap work; space can grow with updates, not just active items.

5. Key Takeaways

• For the largest k, use a min-heap: its root is the candidate to evict, not the largest answer.
• For sorted streams, store one head per stream instead of all remaining values.
• A median needs both the ordering and size invariants; balancing sizes alone is insufficient.
• Include frequency maps and stale entries in space analysis. Use (priority, sequence_number, payload) when tied priorities must not compare payload objects.

Continue to Sorting for static selection, Greedy Algorithms when a proof determines which candidate to choose, and Stacks & Queues when arrival order determines processing order.