Ordering, Heaps, and Selection

How much order does the query need?

A heap can produce full order by repeated extraction, but it does not store that order at rest. Do not read its array as a sorted list. Conversely, a one-time sort can be simpler when the data will not change and many rank queries follow.

Define a consistent comparison key. Equal-key records may be interchangeable for one query and require stable arrival order for another. Values such as NaN need an explicit policy because ordinary numeric comparisons do not supply the assumed order.

Insert into a sorted prefix

Insertion sort keeps the processed prefix sorted. Take the next value, move larger prefix values right and put the value into the resulting gap.

def insertion_sort(values):
    for i in range(1, len(values)):
        current = values[i]
        j = i - 1
        while j >= 0 and values[j] > current:
            values[j + 1] = values[j]
            j -= 1
        values[j + 1] = current
    return values

This function mutates and returns the same list. Keys must supply a consistent order. Empty and singleton lists need no movement.

The strict comparison does not move an equal earlier value past the new value, so this version is stable. Its best case is linear on an already ordered array; reverse order requires quadratic shifts. It uses constant auxiliary storage when values are moved in place.

Nearby order matters: each shift removes an inversion, a pair that appears in the wrong relative order. Tiny or nearly ordered inputs can make insertion attractive without making it a good general quadratic sort for large arbitrary data. Sorted-prefix invariant and inversion cost ↗

Merge ordered halves

Merge sort recursively orders both halves, then compares their current heads. The smaller head is the next output because every later value in either half is at least its own head. Exhausting one side leaves a suffix that can be copied directly.

The base case is a range of zero or one value, not necessarily a pair. Choosing the left head when keys tie preserves source order in the usual stable merge. Each level moves O(n) values, and there are O(log n) balanced splitting levels.

The usual array version costs O(n log n) time and O(n) auxiliary merge storage, plus recursion state. Bottom-up merging instead combines runs of length 1, then 2, 4 and so on. Variants can skip an already ordered boundary, but that optimization is not part of every implementation. Merge and evaluation order ↗

Partition before sorting both sides

Quicksort uses the opposite divide-and-conquer sequence: partition first, then sort the resulting sides. A pivot partitions values according to their relation to it. Partitioning is not itself a complete sort.

Different partition routines promise different boundaries. Lomuto moves a pivot to the end, scans values below it and places the pivot at one final rank. A crossing-pointer partition can return a split boundary instead. Read the routine's contract before using p−1/p+1 recursion bounds.

Duplicate keys can produce poor progress in a naive two-way scheme. Three-way partitioning establishes less-than, equal and greater-than regions. Quicksort then recurses only on the two unequal regions; every value in the equal block is already at an appropriate rank.

Balanced partitions produce O(n log n) work. Repeatedly removing one element produces O(n²) work and linear recursive depth. Random pivots reduce adverse-input dependence; they do not remove the worst case. Median-of-three and tiny-range insertion cutoffs are engineering choices, not universal speedup guarantees. Partition contracts and duplicate handling ↗

Measured speed depends on implementation, key cost, memory access and input distribution. The older “two to three times faster than merge sort” statement is not a general property of quicksort.

Select only the side containing the rank

Selection reuses partitioning but explores only the region containing the requested rank. Use zero-based k for the k-indexed smallest value. A one-based r-th largest query maps to k=n−r; duplicate occurrences count separately unless a distinct-value rank is requested.

# After partitioning active inclusive bounds [lo, hi]:
if k < equal_start:
    hi = equal_start - 1
elif k > equal_end:
    lo = equal_end + 1
else:
    return pivot

Maintain an interval containing the desired global rank. Values discarded on the left belong before every remaining answer candidate; discarded right values belong after it. When k is inside the equal block, return its value without selecting among identical occurrences.

The original [3,2,1,5,4] example asks for k=1. Partitioning around 3 places it at rank 2; only the smaller side matters. Partitioning that side around 2 fixes rank 1 and returns 2.

Randomized selection has expected linear work under the standard pivot model and suitable equal-key handling. The illustrative n+n/2+n/4 sum assumes balanced progress; it is not a proof that every random step halves the input. Naive strict Lomuto partitioning on all-equal values can remain quadratic even with a random pivot.

Worst-case work is O(n²) for these simple pivot strategies. Iterative selection uses constant auxiliary state in-place; recursive depth can be O(n), not an unconditional O(log n). Deterministic median-of-medians can guarantee linear work but uses a different pivot procedure. The lab chooses the first active value for reproducibility, not as a recommended random policy.

Reject an empty array or out-of-range rank. Partitioning mutates the input; use a copy when caller order must survive. The implementation below keeps the same strict Lomuto partition, but uses an iterative selection loop to avoid recursion depth.

A heap orders parent–child paths, not siblings

Every descendant of a min-heap root is reached through nondecreasing parent–child edges, so the root is a minimum. Siblings need not be ordered. A max-heap reverses the inequality and exposes a maximum.

Peek reads the root in O(1). Push adds a leaf and moves it upward while its parent is worse. Pop removes the root, moves the last leaf into that slot and moves it downward through the better child. Choose the better of both children, not just the first one.

Both repairs follow a path of height O(log n). The partially ordered tree is the data structure; the priority queue is the abstract insert/extract behavior it implements. An ordinary FIFO queue instead returns arrival order.

Repair one path; build from the bottom

Repeated pushes build a heap in O(n log n) worst-case work. Bottom-up heapify starts from the last internal node and repairs downward. At each repair, both child subtrees are already heaps.

Heapify changes array order in place. Heapsort then repeatedly moves the extreme root to its final position and repairs the remaining heap. It is a way to produce full order, so “a heap is never used to sort” would be false. Repair paths and heap construction ↗

Separate priority from payload and ties

Python heapq's ordinary operations use a min-heap. Numeric negation implements maximum-priority behavior on older versions. Python 3.14 added native functions such as heapify_max, heappush_max and heappop_max; choose an API supported by the runtime. Current heapq API ↗

from heapq import heappush, heappop
from itertools import count
queue, sequence = [], count()
heappush(queue, (priority, next(sequence), payload))
priority, arrival, payload = heappop(queue)

This fragment assumes priority and payload exist. Tuples compare lexicographically. A unique sequence number breaks equal-priority ties without comparing arbitrary payload objects; it can also preserve arrival order among equal priorities.

Store (−frequency,value) when maximum frequency comes first and value is the intended tie key. Negating only a numeric priority does not negate a whole record's ordering policy. Do not silently let a payload's incidental comparison decide ties.

For numeric min-priority, the original [5,1,8,3] example heapifies the array, extracts1, inserts2 and exposes2 at the root. For numeric max-priority on older APIs, negate on insertion and negate again on reading or removal:

values = [5, 1, 8, 3]
max_heap = [-x for x in values]
heapify(max_heap)
largest = -heappop(max_heap)  # 8
heappush(max_heap, -7)
top = -max_heap[0]  # 7

This fragment assumes heapq functions were imported. An empty heap cannot be peeked or popped. Negation adapts numeric priorities; it does not reverse arbitrary payload comparisons. Ordinary min-heap insertion of5,2,8 produces extraction order2,5,8.

With (priority,task) pairs (2,“task-b”), (1,“task-a”), (3,“task-c”), the first extraction is (1,“task-a”). Using (−10,“urgent”) and (−3,“normal”) instead selects urgent first; negate the returned numeric key to recover its positive priority. Equal numeric keys fall through to later tuple fields, so use the unique arrival counter above when payloads are dictionaries or other noncomparable objects.

heappushpop adds a value then removes the minimum. heapreplace removes the current minimum then adds a value, even when that new value is smaller. For retaining larger candidates, unconditional heapreplace can therefore evict a better value. Use an explicit boundary check or the push/pop policy appropriate to the objective.

Expose the weakest retained candidate

To keep the k largest seen values, use a min-heap of at most k. Its minimum is the weakest retained candidate. Add a new value and remove the minimum if capacity is exceeded.

from heapq import heappush, heappop
def largest_k(values, k):
    if type(k) is not int or not 0 <= k <= len(values):
        raise ValueError("k outside 0..n")
    heap = []
    for value in values:
        heappush(heap, value)
        if len(heap) > k:
            heappop(heap)
    return heap  # Retained, but not sorted.

def kth_largest(values, rank):
    if type(rank) is not int or not 1 <= rank <= len(values):
        raise ValueError("rank must be an integer in 1..n")
    return largest_k(values, rank)[0]

from collections import Counter
from heapq import heappush, heappop

def top_k_frequent(values, k):
    counts = Counter(values)
    if type(k) is not int or not 0 <= k <= len(counts):
        raise ValueError("k must be an integer in 0..distinct count")
    heap = []
    for value, frequency in counts.items():
        heappush(heap, (frequency, value))
        if len(heap) > k:
            heappop(heap)
    return [value for frequency, value in heap]

After t inputs, the heap contains the min(k,t) largest occurrences of that prefix. Removing the smallest among k+1 candidates preserves that invariant. Once k values exist, the root is the kth largest; before then that rank is undefined.

For k smallest, reverse the heap direction so the largest retained value is easiest to evict. k=0 returns an empty selection, but a kth-element query needs 1≤k≤n. Sorting the final heap into rank order is additional work.

A numeric stream costs O(n log(max(2,k))) work and O(k) auxiliary storage. Top-frequency selection first counts distinct values: with m distinct keys, include O(m) count storage and the input counting cost before the m candidate heap updates. A frequency bucket can be another option under the count-domain contract; a heap is not always best.

One head per sorted source

Each nonempty sorted source contributes its first unconsumed value. Every later value in that source is at least this head. Therefore the smallest remaining value overall must be one of the current heads.

from heapq import heappush, heappop

def merge_k_sorted_lists(streams):
    heap, output = [], []
    for source, values in enumerate(streams):
        if values:
            heappush(heap, (values[0], source, 0))
    while heap:
        value, source, index = heappop(heap)
        output.append(value)
        next_index = index + 1
        if next_index < len(streams[source]):
            heappush(heap, (streams[source][next_index], source, next_index))
    return output

The function assumes sorted, indexable finite sequences with mutually comparable values. It does not mutate the sources and returns a new list. Empty sources contribute no head. After extraction, advance only the source that supplied the value. Source/index metadata identifies that successor and gives deterministic tie handling.

For N outputs and K input sources, heapify initialization and extraction cost O(K+N log(max(2,K))) with O(K) frontier storage. Empty sources still require inspection. Materializing the output adds O(N) space; yielding it avoids that retained output. The original repeated-push initialization has its own K log K setup cost.

The same frontier can stop at a requested rank. To find a smallest range containing one value from every source, track the largest current head alongside the smallest. Evaluate their range, then advance the minimum's source; exhaustion of any required source ends complete coverage. The objective is no longer to emit all values.

For linked nodes, store a comparable key and source/tie metadata, not arbitrary nodes in an unqualified equal-key tuple. Preserve node ownership when rewiring; linked-list ownership → owns that distinction.

Keep both boundaries of the middle

Split observed values into lower and upper halves. A max-heap exposes the lower maximum; a min-heap exposes the upper minimum. Use two independent invariants: every lower value ≤ every upper value, and lower has either the same number of values or one more.

Insert on the side determined by the lower maximum. If the size invariant fails, move one boundary value across. Moving lower's maximum to upper or upper's minimum to lower preserves cross-half ordering. Read the median only after these repairs.

The original implementation uses negative values for the lower max-heap. It first inserts on lower, repairs cross-half order, then repairs sizes. The lab chooses the ordered side before rebalancing. Both approaches require both invariants; the update order is part of the implementation.

from heapq import heappush, heappop
from fractions import Fraction

class MedianFinder:
    def __init__(self):
        self.small, self.large = [], []
    def addNum(self, value):
        heappush(self.small, -value)
        if self.large and -self.small[0] > self.large[0]:
            heappush(self.large, -heappop(self.small))
        if len(self.small) > len(self.large) + 1:
            heappush(self.large, -heappop(self.small))
        elif len(self.large) > len(self.small):
            heappush(self.small, -heappop(self.large))
    def findMedian(self):
        if not self.small:
            raise ValueError("median is undefined for an empty stream")
        if len(self.small) > len(self.large):
            return -self.small[0]
        return Fraction(-self.small[0] + self.large[0], 2)

Insert costs O(log n), query O(1), retained values O(n). For exact integer arithmetic, the even answer may be a half-integer. Large fixed-width values need an overflow-safe average; floating-point implementations still have representation limits.

A sliding median additionally deletes outgoing occurrences. Size counts must track logical active values, not stale physical entries. Prune invalid roots before comparisons, moves and queries. Sliding-window contracts → determine which occurrence leaves.

Invalid entries are not active work

A plain heap does not cheaply find an arbitrary payload to delete or update. Maintain an external identity/version map or deletion count, leave old entries physically stored and discard them when they reach the root.

Changing a priority in place can break heap order. Push a new version instead and mark the old version invalid. Before returning a root, verify that its identity/version is still active. Duplicate numeric values may require occurrence identifiers or counts; a single set of values can discard the wrong copy.

Stale entries can increase physical memory beyond the active queue size. Include their insertion/removal costs in accounting; rebuild from active entries when the application needs bounded memory. A bounded active set alone does not bound a lazy heap's physical size.

In Dijkstra →, an old distance entry becomes stale after improvement. First insertion does not finalize a distance. In room counting →, the heap holds active finish events, not generic available work. A heap supplies order; correctness comes from the owning algorithm's state meaning.

Costs follow the operation and the contract

Test empty/singleton data, all equal values, already sorted and reverse order, negative values, $k=0$ or $k=n$, exhausted sources and equal-priority noncomparable payloads. Compare small selections and prefix medians with full sorting; check intermediate invariants as well as final answers.

Binary search → benefits from a full sorted order or a monotone predicate. Graph algorithms → use ordered frontiers for weighted paths and spanning trees. The structure is shared, but neither objective follows from the heap alone.

Sources and related mechanisms

Python heapq operations and API conditions ↗ · Partitioning variants ↗ · Selection by rank ↗ · Original mixed-note video reference ↗

Exact binary-search walkthrough → · DFS and BFS frontiers → · When local cost fails →

The traces are exact small synthetic inputs, not empirical speed comparisons. The callable pattern examples above include their initialization and answer query.