數據流中位數 (對頂堆)

引言：「中間人」問題

尋找已排序陣列的中位數很簡單 ($O(1)$)。但如果數據是一個流呢？

• 每次都排序： 每個新項進入都要耗費 $O(N \log N)$。太慢。
• 維護有序陣列： 每次插入都需要 $O(N)$ 的位移操作。面對數百萬個點依然太慢。

對頂堆 (Two Heaps) 模式允許你在 $O(1)$ 時間 內找到中位數，並在 $O(\log N)$ 時間 內添加新元素。她是即時統計監控的黃金標準。

演算法要解決什麼問題？

• 輸入： 連續不斷的數字流。
• 輸出： 任意時刻的當前中位數。
• 承諾： 在插入和查詢之間取得完美的性能平衡。

核心思想 (直覺版)

將數據分為兩半：

1. 下半部分： 將較小的一半數據儲存在 大頂堆 (Max-Heap) 中。這些小數字中最大的那個就在堆頂。
2. 上半部分： 將較大的一半數據儲存在 小頂堆 (Min-Heap) 中。這些大數字中最小的那個就在堆頂。

中位數 永遠要麼是其中一個堆的堆頂（如果總數是奇數），或者是兩個堆頂的平均值（如果總數是偶數）。

演算法是如何工作的？

1. 平衡： 保持兩個堆的大小幾乎相等（差值 $\le 1$）。
2. 插入：
   • 將新數字添加到合適的堆中。
   • 如果堆變得不平衡，將較大堆的堆頂「移動」到較小的堆中。
3. 尋找中位數：
   • 如果總數是奇數，返回較大堆的堆頂。
   • 如果總數是偶數，返回 (大頂堆.top + 小頂堆.top) / 2。

典型業務場景

• ✅ 性能分析： 隨著請求湧入，即時計算 Web 服務的「中值響應時間」。
• ✅ 金融科技： 在波動市場中即時計算資產的中值價格。
• ✅ 互動式數據應用： 在使用者上傳數據時，儀表板即時更新統計指標。

性能與複雜度總結

• 添加元素： $O(\log N)$。
• 尋找中位數： $O(1)$。
• 空間： $O(N)$，需要儲存所有項。

小結：一句話記住它

「對頂堆模式就像一把天平。透過將數據拆分為兩個對立的堆，她讓『中間人』（中位數）始終坐在堆頂，讓你能瞬間看到她。」