題幹與適用場景
輸入不是一次性陣列，而是持續到達的整數流。結構需要 addNum(x) 與 findMedian()，不能每次重新排序全部資料。題目考察能否從「需要兩側順序資訊」推導雙堆，而不是只背答案。
面試官考察點
面試官關注兩個堆的分工、大小平衡、頂部順序不變量、偶數長度規則和重複值處理。強回答會先確認是否保存全部元素、數值範圍、執行緒安全和近似結果，再給出 O(log n) 插入、O(1) 查詢與 O(n) 空間證明。
回答前需要釐清的問題
- 資料流是否無界？允許保存所有元素，還是必須用滑動視窗或近似摘要？
- 中位數定義是偶數元素的平均，還是下中位數/上中位數？
- 輸入可能超出 64 位整數嗎？平均值會溢位嗎？
- 是否需要刪除、撤銷、時間視窗或並發呼叫？
- 空流應拋錯、返回空值，還是由呼叫方保證先插入？
30 秒回答框架
「我維護 max-heap low 保存較小一半，min-heap high 保存較大一半，保持 low.top <= high.top 且大小差不超過 1。插入後放入適當堆，再平衡大小；奇數返回中間值，偶數返回兩個頂部的安全平均。每次插入 O(log n)，查詢 O(1)，空間 O(n)。 」
分步深入解答
第一步：固定中位數語意
常見定義是奇數取唯一中間值，偶數取兩個中間值平均。面試開始就寫清楚，避免實作正確卻與題目約定不同。近似分位數是另一道題。
第二步：定義兩個堆
low 是最大堆，存較小半部；high 是最小堆，存較大半部。所有 low 元素都不大於 high 元素，重複值只要維持不變量即可。
第三步：設計插入路徑
若 low 為空或 x <= low.top，放入 low，否則放入 high。再移動一個頂部元素修復大小差，不需掃描全部資料。
第四步：保持大小平衡
讓 low 大小等於或比 high 多一。low 多兩個就移動頂部到 high；high 多一個以上就移動頂部到 low。
第五步：處理查詢與數值安全
空流返回明確錯誤。奇數返回 low 頂部；偶數計算兩個頂部平均，先轉更寬型別或使用不溢位公式。
第六步：證明複雜度
插入執行常數次堆 push/pop，每次 O(log n)；查詢只訪問一或兩個頂部，O(1)；兩個堆合計保存 n 個元素，空間 O(n)。
第七步：說明替代方案
有序陣列插入 O(n)，平衡樹可做到 O(log n) 插入與排名查詢，計數直方圖適合值域很小，近似摘要適合允許誤差的無界流。
第八步：用邊界測試驗證
測試空流、單元素、偶數、重複值、負數、單調序列和極值。每次插入後斷言堆大小差、頂部順序和返回值；並發時測試鎖邊界。
偽代碼
add(x):
if low.empty() or x <= low.max(): low.push(x)
else: high.push(x)
if low.size() > high.size() + 1: high.push(low.pop())
if high.size() > low.size(): low.push(high.pop())
median():
if low.size() > high.size(): return low.max()
return safe_average(low.max(), high.min())設計取捨與邊界
| 方案 | 插入 | 查詢 | 適用邊界 |
|---|---|---|---|
| 雙堆 | O(log n) | O(1) | 精確、線上、保存全部資料 |
| 有序陣列 | O(n) | O(1) | 資料量小、實作簡單 |
| 平衡樹 | O(log n) | O(1)/O(log n) | 還需要刪除或排名 |
| 近似摘要 | 近似 | 近似 | 無界流且允許誤差 |
雙堆不支援高效刪除任意舊值；滑動視窗需要延遲刪除或其他結構。它也不提供持久化、分散式一致性或跨機器合併。
落地計畫與證據
先實作雙堆和邊界測試，再加入溢位保護與指標。公開面試資料將此題描述為線上 order-statistics；TechInterview 與 Intervu 都將 two-heaps 作為典型流式資料結構。
試點退出條件
邊界測試通過；隨機序列中不變量成立；延遲和記憶體符合預算；極值不溢位；空流行為明確。
如何證明收益不是巧合
與每次全量排序基線比較插入吞吐、p95 延遲、峰值記憶體和結果一致性，使用相同隨機種子覆蓋多種分布。
常見誤區與追問
每次插入都排序全部資料
插入變成 O(n log n)，不適合持續流。雙堆只維護邊界資訊。
只要求兩堆大小相同
還要保持 low.top <= high.top，否則頂部不一定是中位數。
忽略偶數長度定義
要明確平均、下中位數或上中位數，並處理型別轉換和溢位。
如何支援滑動視窗？
用計數表標記過期元素並在堆頂清理，或使用支援排名的平衡樹，重新說明複雜度。
無法保存全部資料怎麼辦？
允許誤差就用分位數摘要；要求精確中位數就必須保存足夠順序資訊，不能宣稱一般問題可用常數空間。
多執行緒如何保持一致？
用讀寫鎖或單執行緒事件迴圈保護兩個堆與不變量，查詢不能讀到只更新一邊的狀態。