Heap (Priority Queue)

Core Concepts

Heap — a complete binary tree satisfying the heap property: every node's key compares correctly with its children's keys. "Complete" means all levels are filled except possibly the last, which fills left-to-right.

Min-Heap — parent ≤ both children at every node; the minimum element is always at the root.

Max-Heap — parent ≥ both children at every node; the maximum element is always at the root.

Priority Queue — the abstract data type that a heap implements: insert arbitrary elements, always extract the element with highest priority (min or max).

Heapify — the process of repairing the heap property at a node by swapping downward (sift-down) or upward (sift-up).

Heap size vs. array size — heap occupies heap_size elements of the underlying array; elements beyond heap_size are logically outside the heap.

k-th order statistics — heap's key application: find/maintain the k-th smallest or largest element in O(log n) per update.

---

Structural Invariants

---

Internal Representation

Array-based (canonical) — the complete-binary-tree structure maps bijectively to a contiguous array. No pointers needed. For 0-indexed arrays:

left  = 2*i + 1
right = 2*i + 2
parent = (i - 1) // 2

Space: O(n). All heap operations use only index arithmetic; cache-friendly.

Pointer-based — each node holds left, right, parent pointers. Required for mergeable heaps (Fibonacci, binomial). Never used for standard binary heaps because index arithmetic is cheaper.

d-ary heap — each node has d children instead of 2. Reduces tree height to log_d(n), cutting sift-down cost (fewer levels) but increasing per-level comparison cost (d comparisons per node). Useful when push-heavy workloads dominate: 4-ary or 8-ary heaps reduce the sift-down work that pop triggers.

---

Types / Variants

For LeetCode, the binary heap (via heapq) covers every problem. Fibonacci/binomial heaps are theoretical knowledge only.

---

Topic-Specific Operations

Push (sift-up)

Insert the new element at the next array position (end of heap). Bubble it up: compare with parent; swap if heap property violated; repeat until root or property holds. Time: O(log n).

Pop (sift-down / extract-min/max)

Swap root with the last element, decrement heap size, then sift-down the new root: compare with smallest (min-heap) or largest (max-heap) child; swap if property violated; repeat until leaf or property holds. Time: O(log n).

Peek

Return heap[0] without modification. Time: O(1).

Heapify (build-heap)

Convert an arbitrary array into a heap in O(n) by calling sift-down on every non-leaf, starting from the last non-leaf (n//2 - 1) down to index 0.

for i in range(n//2 - 1, -1, -1):
    sift_down(heap, i, n)

Why O(n): half the nodes are leaves (0 swaps); height-h nodes do O(h) work; summing over all levels gives O(n). Contrast with n individual pushes: O(n log n).

Decrease-key / Increase-key

Change a key then sift-up (if decreased in min-heap) or sift-down (if increased). Requires knowing the element's index — not directly supported by Python's heapq. Use the lazy-deletion pattern instead.

Delete arbitrary element

Swap target with last element, decrement heap size, then sift-up or sift-down as needed. Also requires index tracking.

---

Key Algorithms

Heap Sort

Build a max-heap with heapify O(n), then repeatedly extract the max and place it at the end of the array. O(n log n) time, O(1) space. Not stable.

Key insight: after heapify, heap[0] is the max; swapping it to position n-1 and sifting down over n-1 elements repeats the extraction.

K-th Smallest / Largest Element

Using a size-k max-heap (k-th smallest): push elements one by one; if heap size exceeds k, pop. The root is always the k-th smallest seen so far. O(n log k) time.

Using quickselect: average O(n) — see quickselect.md if it exists.

Merge K Sorted Lists / Arrays

Push the first element of each list with its list index into a min-heap. On each pop, push the next element from that list. O(N log k) where N = total elements, k = number of lists.

Sliding Window Minimum / Maximum

Monotonic deque is O(n) and preferred; heap approach is O(n log n) but simpler: use a min-heap with lazy deletion — mark popped elements as invalid when they fall outside the window.

Top-K Frequent Elements

Count frequencies with a hash map, then use a size-k min-heap on frequencies. O(n log k) time. For k close to n, counting sort or bucket sort is faster.

Median of Data Stream

Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half, sizes differing by at most 1. Median is either the max-heap root or the average of both roots. Each insertion O(log n).

---

Advanced Techniques

Lazy Deletion (Dead Entry Pattern)

Problem class: Modify or remove arbitrary heap elements without direct index access (e.g., sliding window max, Dijkstra with re-relaxation, task scheduling with cancellation).

Mechanism: When an element becomes invalid, do not remove it from the heap. Instead, mark it as deleted (e.g., via a valid set or a counter dict). On each pop, discard entries that are marked invalid before processing.

When to use over alternatives: Use when you need a conceptually simple heap but elements can become stale. Avoid it when the invalid-entry fraction is large (memory and log factor bloat); prefer a heap with explicit decrease-key support or a sorted container (SortedList) instead.

Complexity: O(log n) amortised per operation if invalid entries are bounded; worst-case O(n log n) if all entries are invalidated before popping.

Two-Heap Partition

Problem class: Dynamic median, or problems requiring simultaneous access to the minimum of the upper half and maximum of the lower half of a stream.

Mechanism: Maintain lo (max-heap) and hi (min-heap) with the invariant len(lo) == len(hi) or len(lo) == len(hi) + 1. On insert: route to correct half, then rebalance by moving the root of the larger heap to the smaller one if sizes diverge by 2.

When to use: Only when you need O(1) access to both the lower-half maximum and upper-half minimum simultaneously. For k-th element alone, a single size-k heap is simpler.

Complexity: O(log n) insert, O(1) median query.

K-Way Merge via Heap

Problem class: Merge k sorted sequences, smallest-range-covering-k-lists, external sort.

Mechanism: A min-heap of size k holds one "frontier" element per sequence. Each pop yields the global minimum; push the next element from the same sequence.

When to use over alternatives: Use when k sequences are pre-sorted. For unsorted data, merge-sort directly. For k=2, a two-pointer merge is O(n) and faster.

Complexity: O(N log k) time, O(k) space.

Heap + Hash Map (Index-Tracked Heap)

Problem class: Problems requiring decrease-key or arbitrary deletion that Python's heapq doesn't natively support (e.g., Dijkstra with edge weight updates, LFU cache).

Mechanism: Maintain a dict {value: index_in_heap}. Update on every swap during sift operations. Allows O(log n) decrease-key.

When to use: Only when lazy deletion's memory overhead is unacceptable and the number of decrease-key operations is large. Implementation complexity is high; reach for it only after lazy deletion proves insufficient.

Complexity: O(log n) all operations; O(n) space for the index map.

Scheduled / Event-Driven Simulation

Problem class: CPU scheduling, task ordering, meeting rooms, event timelines where events fire at computed future times.

Mechanism: Heap is ordered by event time. Pop the soonest event, process it, push any new events it generates. Continue until heap is empty or target time reached.

When to use: When events are generated dynamically (each processed event can create future events). If events are all known upfront and require sorting only, a sort + sweep is simpler.

Complexity: O(E log E) where E is the total number of events.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Empty heap pop: calling heapq.heappop on an empty list raises IndexError. Always guard with if heap or use heappop only when size is known positive.

• Single-element heap: heappop returns that element and leaves an empty list — safe, but follow-up heap[0] will crash. Check length before peek.

• Negative value negation overflow: negating float('inf') gives -float('inf') which is fine; negating Python int has no overflow. But negating the sentinel value itself (e.g., using -sys.maxsize - 1) can cause subtle errors if compared against original values.

• Tuple comparison tie-breaking: heapq compares tuple elements left-to-right. If the second element is a non-comparable object (e.g., a custom class without __lt__), push fails with TypeError. Always include a numeric tie-breaker as the second tuple element, e.g., (priority, counter, item).

• Lazy deletion memory leak: if invalidated entries are never popped (because valid entries keep arriving), the heap grows unboundedly. Set a memory budget or periodically drain.

• Heapify modifies in place: heapq.heapify(lst) mutates lst. If the original list must be preserved, copy first.

• Heap[0] != minimum after direct mutation: modifying heap[0] directly (e.g., heap[0] = x) without calling heapq.heapreplace or heapq.heappush breaks the invariant silently. Always use heapq functions.

• Off-by-one in k-th element: "k-th smallest" with a max-heap of size k — the root is the answer only after processing all n elements, not mid-stream unless the problem guarantees it.

• Two-heap balance condition: after an insert, exactly one rebalancing push is needed. Doing two rebalances (one per heap) introduces bugs. The invariant: sizes differ by at most 1; lo can be equal to or one larger than hi.

---

Implementation Notes

• heapq is a min-heap only. Negate values to simulate a max-heap; remember to negate on pop.
• heapq.heapify is O(n) in-place. heapq.nlargest(k, iterable) and nsmallest(k, iterable) are O(n log k) but have constant-factor overhead vs. manual heap operations.
• heapq.heapreplace(heap, item) pops the min and pushes the new item in one call — more efficient than a pop + push when the new item is likely larger than the popped one (avoids an extra sift).
• heapq.heappushpop(heap, item) pushes then pops — useful when item is likely smaller than the current min (avoids pointless insertion).
• Python recursion limit is 1000 by default; heap operations are iterative, so no risk here.
• SortedList from sortedcontainers supports O(log n) insert/delete/index — useful when you need arbitrary deletion or rank queries that heaps cannot provide.
• For Java: PriorityQueue is a min-heap; for max-heap pass Collections.reverseOrder(). poll() is pop, peek() is peek. Initial capacity constructor avoids resizing.
• For C++: priority_queue<T> is a max-heap by default; priority_queue<T, vector<T>, greater<T>> is min-heap.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

K-th Order Statistics

• Kth Largest Element in an Array (215)
• Kth Largest Element in a Stream (703)
• K Closest Points to Origin (973)
• Find K Pairs with Smallest Sums (373)
• Kth Smallest Element in a Sorted Matrix (378)

Top-K Frequency

• Top K Frequent Elements (347)
• Top K Frequent Words (692)
• Sort Characters By Frequency (451)

Merge K Sorted

• Merge K Sorted Lists (23)
• Smallest Range Covering Elements from K Lists (632)
• Find K-th Smallest Pair Distance (719)

Streaming / Two-Heap

• Find Median from Data Stream (295)
• Sliding Window Median (480)
• IPO (502) — two-heap greedy

Scheduling / Simulation

• Task Scheduler (621)
• Reorganize String (767)
• Meeting Rooms II (253)
• Process Tasks Using Servers (1882)
• Single-Threaded CPU (1834)

Graph (Dijkstra / Prim)

• Network Delay Time (743)
• Cheapest Flights Within K Stops (787)
• Path With Minimum Effort (1631)
• Minimum Cost to Connect All Points (1584)

Greedy with Heap

• Last Stone Weight (1046)
• Furthest Building You Can Reach (1642)
• Minimum Number of Refueling Stops (871)
• Trapping Rain Water II (407)

Additional LeetCode Coverage

• Reduce Array Size to The Half (LC 1338)
• Remove Stones to Minimize the Total (LC 1962)
• Maximum Subsequence Score (LC 2542)

Clarification Questions to Ask

• "When you say k-th smallest, is k 1-indexed or 0-indexed?"
• "Can the input contain duplicates, and does the k-th smallest refer to the k-th distinct value or k-th position in sorted order?"
• "Is the input given all at once or as a stream?" (determines static vs. dynamic approach)
• "What's the constraint on k vs. n?" (if k ≈ n, sort may beat a heap)
• "For 'closest', which distance metric — Euclidean, Manhattan, or Chebyshev?"
• "Are edge weights guaranteed non-negative?" (negative weights break Dijkstra)

Common Interview Mistakes

• Using a max-heap for k-th smallest instead of a min-heap of size k — produces wrong answer when new elements smaller than current root arrive.
• Forgetting that Python's heapq is min-heap only and failing to negate for max-heap problems.
• Mixing 0-indexed and 1-indexed formulas when implementing a custom heap — leads to off-by-one in parent/child relationships.
• Not handling the tie-breaking tuple correctly, causing TypeError when two priorities are equal and data is non-comparable.
• In two-heap median, performing two rebalances per insert instead of at most one — results in an off-by-one in sizes.
• In Dijkstra, not skipping already-visited nodes on pop — causes O(E log E) worst case to become O(E²) if combined with repeated relaxation.
• Calling heapq.heappop on an empty list instead of checking size first.

Typical Follow-Up Escalations

• "Your k-th largest is O(n log k) — can you do better?" → Quickselect gives O(n) average.
• "Now the stream has deletions too, not just insertions." → Lazy deletion pattern with an invalid counter dict.
• "The k changes dynamically." → Maintain two heaps; adjust their sizes on each k change.
• "What if the data doesn't fit in memory?" → External sort or reservoir sampling; heap-based k-way merge for files.
• "Can you make the median query O(1) instead of O(log n)?" → Already O(1) with two-heap (just read both roots); the O(log n) cost is on insert.
• "Dijkstra gave wrong answers on my graph — why?" → Check for negative edges (use Bellman-Ford) or directed vs. undirected mismatch.