Heaps & Priority Queues

Bottom-up heapify turns an array of n items into a heap in O(n) time, while n successive inserts cost O(n log n) in the worst case. Same heap, lower cost, whenever every item is available up front.

A min-heap's array is not sorted. The property constrains only parent versus child, so every root-to-leaf path is non-decreasing while siblings may sit in any order. Only index 0 is guaranteed: it holds the minimum.

A priority queue supports three operations: insert an item with a priority, peek at the top-priority item, and extract that item. A FIFO queue hands back items in arrival order; a priority queue hands back the most urgent one first.

Give the queue a reversed comparison function, or push negated numeric keys. The reversed comparison is safer and self-documenting; negation works only for numeric keys and forces every read site to remember the flip.

Keep only the current head of each of the k streams in a min-heap. Repeatedly extract the smallest, emit it, and push that same stream's next element in its place. The heap never grows beyond k entries.

The heap must be a min-heap because its root is the smallest of the k values you are still keeping — the bar a new value must beat. A max-heap would evict the largest values and leave you the k smallest.

A max-heap holds the lower half of the samples and a min-heap the upper half, so the median sits at the heap tops: O(1) to read, O(log n) to absorb a new sample. A sorted buffer costs O(n) per insert to shift elements.

Sorting the whole catalog costs O(n log n) to answer a question about 100 items. A retained-candidate heap does one pass in O(n log k) with O(k) memory; quickselect averages O(n) but rearranges the input and needs it all resident.

The promoted child becomes the parent of both children, so it must be the smaller one. Promote the left child while the right is smaller and the new parent exceeds its sibling — the property breaks below the swap, where nothing rechecks it.

Sift-down cost tracks a node's height above the leaves, not the tree's height. Half the nodes are leaves and never move, a quarter move at most one level; the heights summed over all nodes total about n.

Level-order layout forces the arithmetic. Level L starts at index 2^L - 1, and the k-th node of a level parents nodes 2k and 2k+1 of the next; substituting collapses to children 2i+1, 2i+2 and parent floor((i-1)/2).

A binary heap does exactly what the priority queue contract asks and no more: it keeps only a partial order, so insert and extract cost O(log n) and peek O(1). Sorted lists pay O(n) per insert; search trees pay pointer and cache overhead for ordering nobody asked for.

Standard-library priority queues expose no decrease-key. Push a fresh entry at the new priority and discard outdated entries when they surface at the top. Mutating a stored key in place does not re-sift the heap and silently corrupts its order.

The heap touches each element twice, at log k cost each. Merging source after source into one growing accumulator re-copies everything already accumulated on every round, so the earliest elements are copied about k times.

Roughly a fourfold smaller log factor: log2(100) is about 6.6 against about 26.6 for 100 million. The real saving is elsewhere — 100 resident values instead of 100 million, in a single forward pass over data of unknown length.

Every value in the max-heap is at most every value in the min-heap, and the two sizes differ by at most one. A single pop-and-push, moving one top from the heavier heap to the lighter one, restores the size part after any insert.

Expected O(n) is an average over pivot choices, not a per-call guarantee: naive pivot rules degrade to O(n^2) on sorted or duplicate-heavy input. Quickselect also permutes the caller's data in place and needs the entire input resident.

Both are O(log n) in the worst case, but insert's sift-up usually stops after a comparison or two, because most nodes already live in the bottom levels. Extract's sift-down starts a bottom-of-the-tree key at the root and usually travels most of the height.

Sift-down only works when both subtrees below a node are already valid heaps. Children sit at higher indices than their parent, so counting indices down guarantees that precondition; running the loop upward can leave the heap property violated.

Completeness is what makes the implicit array work: nodes fill slots 0 to n-1 with no gaps, so index arithmetic replaces pointers and the height stays floor(log2 n). Allow a hole and child indices address emptiness.

Unspecified, and you cannot rely on it. Extract-top promises to return an item of top priority, not a particular one, so items that tie come out in an order set by the operation history. Break ties with a monotonically increasing sequence number to get arrival order.

Seeding from a source that is empty, and refilling from a source that has just run out. Both read past the end of a sequence. Guard the seed loop with an emptiness check and the refill with a has-next check.

Raising d shrinks the height to log_d n, but every sift-down level must find the smallest of d children instead of two. Extract-min cost grows as d over log d, so a wider heap makes sift-up cheaper and sift-down dearer.

An indexed heap maps each element's identity to its current array slot, so reprioritizing a queued element costs O(log n): O(1) to locate it, then one sift. A plain heap must scan O(n) to find it first.

Flag it, but on facts rather than asymptotics: with every record in hand, the bulk build is a one-line change from O(n log n) worst case to O(n). Check first how records arrive and what share of the job construction is.

The heap invariant relates a node only to its own children, never one subtree to another, so an in-order walk emits an arbitrary sequence. Ranked output costs O(n log n) by removing the root n times.

Rebuild the queue. Every queued item sits at a position justified by the old comparison, so swapping the rule in place leaves the structure inconsistent. Take the existing elements and re-establish the invariant under the new rule, which costs O(n) with a bulk build.

Removing a named element from a heap-backed queue is O(n): only the top is addressable, so the element must be found by scanning. Called once per cancelled item in a loop, that is quadratic work hidden behind an innocuous-looking call.

None. A heap is not stable, so equal keys from different sources come out in an order determined by internal array positions. Order within a single source is preserved automatically; across sources you must extend the comparison key to get determinism.