Heap and Priority Queue

A heap is a concrete data structure—usually a binary tree stored in an array—that guarantees the heap property: each parent is ≤ (min‑heap) or ≥ (max‑heap) its children. A priority queue (PQ) is an abstract ADT that supports push, pop, and sometimes decrease‑key. The mismatch appears when you reach for std::priority_queue in C++ or java.util.PriorityQueue expecting a decrease‑key operation; those libraries expose only add/poll, making key updates O(n). When the interview problem requires updating priorities (e.g., Dijkstra’s algorithm), you either implement a binary heap yourself or switch to a Fibonacci heap for O(1) amortized decrease‑key. Conversely, for “give me the k‑largest elements” a library PQ suffices and saves you from reinventing the wheel. In short, choose a custom heap when you need fine‑grained control or non‑standard ops; choose a language PQ for plain extract‑min/max.

A binary heap lives in a flat array. For a 0‑based layout, the parent of index i is (i-1)//2, the left child is 2*i+1, and the right child is 2*i+2. In a 1‑based layout (common in textbook proofs) the formulas become parent = i//2, left = 2*i, right = 2*i+1. The choice of base determines every loop bound. A typical interview bug is writing while (i > 0 && heap[parent(i)] > heap[i]) but using the 1‑based formulas, which causes an out‑of‑range access at index 0. Below is a concrete insertion of the sequence [7, 3, 5, 1] into an empty 0‑based heap, showing the index calculations at each sift‑up step. The final array [1,3,5,7] satisfies the min‑heap property.

Worked example:
1. Insert 7 → [7] (i=0, no parent).
2. Insert 3 → [7,3]; parent(1)=0 → swap → [3,7].
3. Insert 5 → [3,7,5]; parent(2)=0 (3 ≤ 5) → stop.
4. Insert 1 → [3,7,5,1]; parent(3)=1 (7 > 1) swap → [3,1,5,7]; now parent(1)=0 (3 > 1) swap → [1,3,5,7].
The index math is explicit at each step, eliminating the classic off‑by‑one confusion.

The three fundamental operations share a common invariant: after each call the array must satisfy the heap property. Insert appends the new key at the end and sifts it up using the parent formula; this costs at most the height of the tree, ⌊log₂ n⌋. Extract‑Min (or Max) swaps the root with the last element, removes the last, then sifts the new root down, comparing with the smaller (or larger) child at each level—again O(log n). Decrease‑Key is trickier. In a binary heap you locate the element (often by storing its index externally), replace its value with a smaller key, and sift‑up, costing O(log n). Fibonacci heaps achieve O(1) amortized decrease‑key by cutting the node and adding it to a root list, but their constant factors make them rarely the right choice for interview code. When a problem explicitly asks for “update priorities”, mention the trade‑off and either implement a binary‑heap decrease‑key or explain the Fibonacci alternative.

Worked example: Starting from [1,3,5,7], decrease the key at index 2 (value 5) to 2. After replacement we have [1,3,2,7]; sift‑up swaps with parent index 0? parent(2)=0, 1 ≤ 2, so no swap. The heap now [1,3,2,7] is still valid because 2 is larger than its parent 1 but smaller than its child (none).

When the entire input is known up front, the naïve approach—insert each element individually—costs O(n log n). Floyd’s algorithm, introduced in 1964, starts from the last non‑leaf node (n//2‑1) and runs heapify_down on each index moving backwards. The proof (see Wikipedia) shows the total work telescopes to Θ(n). A quick benchmark illustrates the gap: for a random array of 100 000 integers, heapq.heapify in Python finishes in ~0.012 s, while inserting one‑by‑one takes ~0.035 s, roughly a 3× slowdown. In interviews, if the problem statement says “you are given an array of N numbers, return the heap”, immediately mention heapify and write heapq.heapify(arr) (Python) or make_heap(begin, end) (C++). Only fall back to repeated inserts when the input arrives as a stream.

Benchmark snippet (Python):

The binary heap is a 2‑ary tree, giving a height of ⌊log₂ n⌋. A d‑ary heap replaces each node with d children, reducing the height to ⌊log_d n⌋ and thus fewer sift‑up/down levels. However, each level now examines d children, increasing constant factors. For Dijkstra on dense graphs, a 4‑ary heap often beats a binary heap because the reduced height outweighs the extra comparisons. Binomial heaps support O(log n) merge by maintaining a collection of binomial trees; they are rarely asked directly but appear in “mergeable priority queue” problems. Fibonacci heaps shine when the algorithm performs many decrease‑key operations (e.g., Dijkstra with a dense edge set). Their amortized O(1) decrease‑key and O(log n) delete‑min can halve runtime, but the implementation is complex and the hidden constants make them unsuitable for most coding‑rounds. Use a binary heap unless the interview explicitly calls for many key updates or a merge operation; then mention d‑ary or Fibonacci as possible optimizations.

Each mainstream language wraps a binary heap in a slightly different API. Java’s `PriorityQueue` is a min‑heap backed by a 0‑based array and does not provide a decrease‑key method; you must remove and re‑insert the element, which is O(n). The docs confirm this limitation. C++ `std::priority_queue` is a max‑heap by default; you can flip it with std::greater<> or store std::pair<priority, value> and provide a custom comparator. Under the hood it uses std::make_heap, push_heap, and pop_heap. Python’s `heapq` is a plain list implementing a min‑heap; for custom ordering you pack (priority, item) tuples, or use dataclasses with order=True. Beware that heapq does not support decrease‑key; the typical workaround is to push a new entry and lazily discard stale ones during heappop. When interviewers ask for “update priority”, point out these language constraints and either implement your own heap class or explain the lazy‑deletion pattern.

Even a tiny index slip can corrupt the entire structure. Before you submit, run these checks:
1. Heap‑property validator – iterate over all non‑leaf nodes and assert heap[i] <= heap[left] and heap[i] <= heap[right] (or the opposite for max‑heap). 2. Array dump – after each push or pop, print the internal list; visual inspection often reveals a swapped child. 3. Edge‑case suite – include (a) duplicate keys, (b) strictly descending inserts, (c) a single element, (d) an empty heap, and (e) a large random array (N ≥ 10⁴) to stress‑test performance. 4. Decrease‑key sanity – after decreasing a key, run the validator and ensure the element moved upward. 5. Language‑specific quirks – for Java, verify that remove(Object) truly deletes the intended instance; for C++, check that the comparator behaves consistently with the stored type. Running this checklist cuts down the typical “heap property violated after X operations” bugs that interviewers love to expose.

How do you find the k‑largest elements in an unsorted array using a heap?

Maintain a min‑heap of size k. Iterate the array, push each element, and when the heap exceeds k pop the smallest. At the end the heap contains the k‑largest values in O(n log k) time.

Explain how to merge k sorted lists with a priority queue.

Insert the first element of each list into a min‑heap keyed by value. Repeatedly extract the smallest, append it to the output, and push the next element from the same list. This runs in O(N log k), where N is the total number of elements.

Why is building a heap with Floyd’s algorithm preferred when the whole array is given?

Floyd’s bottom‑up heapify runs in Θ(n) time, whereas inserting each element individually costs O(n log n). For large N (≥10⁴) the linear method is 2‑3× faster, as shown in the benchmark.

When would you choose a d‑ary heap over a binary heap in an interview?

When the algorithm performs many sift‑down operations (e.g., Dijkstra on dense graphs). A larger branching factor reduces the tree height, decreasing the number of levels traversed, which can outweigh the extra child comparisons.