Heaps and Priority Queues Questions

Python's heapq implements a min-heap. To get a max-heap, store negated values and invert on pop/push.
Example pushing and popping a max-heap using heapq:

import heapq
max_heap = []
# push value 10
heapq.heappush(max_heap, -10)
# push value 5
heapq.heappush(max_heap, -5)
# pop max (returns 10)
max_val = -heapq.heappop(max_heap)
print(max_val)  # 10

Reasoning: negation flips ordering so the smallest negative corresponds to the largest original value, preserving O(log n) operations of heapq.

Approach: With memory M < N we must approximate median. Options:

1. Reservoir sampling: keep uniform sample size M and compute median of sample. Error: variance depends on sample size; no deterministic bounds on rank-error but unbiased sample approximates distribution; simple to implement.
2. GK (Greenwald-Khanna): deterministic streaming quantile summary providing ε-approximate ranks with O(1/ε log(εN)) space. Guarantees rank error ≤ εN. Good when fixed rank error needed.
3. t-digest: clustering values into centroids with emphasis near tails; excellent practical accuracy for median, small memory, mergeable for parallelism; no strict worst-case rank bounds but very accurate for quantiles.
   Trade-offs: reservoir is simplest but random; GK gives deterministic rank bounds; t-digest best for floating distributions and mergeability. Implementation notes: use GK for strict ε guarantees; use t-digest for real-valued histograms and distributed systems; use reservoir for very constrained systems where probabilistic estimate is acceptable.

Initial heaps: lowers(max): [5,3,2] (root 5), highers(min): [6,8,9] (root 6). Insert 7:

1. Compare 7 to lowers' max (5) or highers' min (6). Since 7 > 6, push into highers.
   highers becomes [6,7,9,8] (heap ordering keeps 6 at root).
2. Rebalance sizes: lowers size=3, highers size=4 → difference =1, acceptable (<=1). No moves required.
   Resulting heaps:

• lowers (max via values): [5,3,2]
• highers (min): [6,7,9,8]
  Median: since highers larger by 1, median = 6.0 (the root of highers). Decision rationale: insert into highers because 7 belongs to larger-half; rebalancing unnecessary because size invariant holds.

Approach: Merge two running-median structures A and B, each with a max-heap L (lower half) and min-heap R (upper half). We must produce heaps L', R' representing the union stream while preserving balance invariants (|L|-|R| in {0,1}) and all elements in L' <= all in R'. Algorithm:

1. Ensure both inputs expose sizes and peek operations. Let nA = |A|, nB = |B|.
2. Create an output empty pair (L',R').
3. Merge by repeatedly extracting the global next element from tops: simulate an ordered merge using the two structures' peek and pop. But popping disturbs originals: instead, iterate by repeatedly comparing A.peek_lowest_upper()/A.peek_highest_lower() and B equivalents to choose next element to push to output heaps.
4. For each chosen element x, push into L' or R' using the standard two-heap insert rule: if L' empty or x <= top(L'), push into L' (max-heap); else push into R'. After each push, rebalance so sizes differ by at most 1.
   Correctness: Because we effectively insert every element into a fresh two-heap structure using the same insertion invariants, resulting medians equal medians of the union. Runtime: Each element from both streams is pushed once and may cause O(log m) heap operations where m is current output size. Total complexity O((nA+nB) log(nA+nB)). Space: O(nA+nB) for new heaps. Optimizations: if heaps are accessible as sorted arrays (e.g., by extracting whole heaps in O(n log n) or converting to arrays), one can perform an O(nA+nB) merge into a sorted array then build two heaps in O(n) by heapify; overall O(nA+nB) time and O(nA+nB) space. Edge cases: if copying originals is expensive, consider destructive merge and reconstruct original if needed. If memory constrained, perform in-place by moving nodes between heap representations when supported.

Situation: In production, a user-facing cache returned inconsistent session lists; a custom balanced tree lost its invariants after concurrent updates.
Task: Identify root cause, restore correctness, and prevent recurrence without long downtime.
Action:

• Reproduced issue in staging with the same concurrent workload and deterministic scheduler.
• Added assertions to detect the tree invariant violations and wrote a diagnostic dump to capture tree state at failure.
• Found a non-atomic update path where two threads concurrently mutated pointers; fixed by introducing a fine-grained lock and refactoring mutation to an atomic replace operation.
• Communicated status to stakeholders: immediate mitigation (feature flag to disable concurrent writers), ETA for fix, and postmortem timeline.
  Result: Bug fixed with no further incidents. Postmortem documented root cause, added unit + stress tests, and monitoring alerts for invariant violations. Team adopted the diagnostic assertions as part of CI.