演算法面試：如何求資料流的動態中位數？

題目與適用情境

設計 MedianFinder，支援兩個操作：

• addNum(num)：將一個整數加入資料流。
• findMedian()：回傳目前所有數字的中位數；元素個數為奇數時回傳中間值，為偶數時回傳兩個中間值的平均數。

假設只有插入，沒有刪除；findMedian() 只會在至少插入一個數字後呼叫。輸入可以包含負數、重複值與 32 位元有號整數，最多執行 50,000 次操作。目標是讓每次插入為 O(log n)、查詢為 O(1)，空間為 O(n)。

例如依序插入 5、2、10、4，每次插入後的中位數分別是 5、3.5、5、4.5。若每次查詢前重新排序， 結果正確，但查詢成本是 O(n log n)；若一直維護排序陣列，查詢只需 O(1)，插入中間位置卻要搬動 O(n) 個元素。

2026 年的公開面試準備資料仍把這題列為兩個 heap 模式的代表性編碼題。它適合一般軟體工程師、後端、 資料與基礎架構職缺的演算法面試。核心不在背出「最大堆積加最小堆積」，而在能否從查詢目標推導資料結構、 說清楚兩個不變量，並解釋固定的搬移順序為何不會破壞分區。

面試官考察重點

第一個訊號是候選人能否從操作比例反推結構。中位數只與排序後的中間位置有關，不需要維護完整順序。為了 O(1) 查詢，兩個中間候選值必須一直位於可直接讀取的位置；heap 頂端正好提供這項能力。

第二個訊號是能否同時維護「分區」與「平衡」：

1. 較小的一半放在最大堆積 lower，較大的一半放在最小堆積 upper，而且 lower 的每個值都不大於

upper 的每個值。

1. lower 的元素數等於 upper，或剛好多一個。

這兩個條件缺一不可。只保證數量接近，兩個 heap 可能裝反；只保證左右順序，大小可能相差太多，heap 頂端 便不再對應中間位置。

第三個訊號是複雜度是否說得精確。一次插入做固定次數的 heap 操作，每次 O(log n)；查詢只讀一個或 兩個頂端，所以是 O(1)。保存全部輸入仍需 O(n) 空間。「資料流」代表線上更新，不代表記憶體為常數。

最後看驗證能力。好的回答會主動測試第一個元素、偶數與奇數長度、重複值、全部負數、單調遞增、單調遞減 及整數極值，也會拿一個慢但明顯正確的排序陣列版本做隨機差分，而不只執行題目範例。

回答前需要釐清的問題

• 只有插入，還是也要刪除舊元素？ 只有插入時兩個普通 heap 足夠；滑動視窗需要延遲刪除或有序多重集合。
• 查詢會在空資料流上呼叫嗎？ 本題保證不會。若正式介面允許空流，應回傳 optional 或丟出明確例外。
• 輸入是整數還是浮點數？ 本題使用整數。浮點數若允許 NaN，比較關係不是全序，必須先定義拒絕或排序規則。
• 偶數個元素如何定義中位數？ 本題取兩個中間值的算術平均數，因此回傳型別要能表示小數。
• 需要精確中位數還是允許近似？ 本題要求精確值；無界資料流且記憶體受限時需改用分位數摘要。
• 數值範圍會讓平均值溢位嗎？ Python 整數不會溢位；固定寬度語言應先轉成更寬型別再做加法與除法。
• 查詢與插入的比例如何？ 高頻查詢適合兩個 heap；若只在輸入結束後查一次，收集後排序通常更簡單。
• 是否需要執行緒安全？ 目前是單執行緒。並行版本要讓兩個 heap 的搬移及查詢看到同一個狀態快照。

30 秒回答框架

「我把較小的一半放進最大堆積 lower，較大的一半放進最小堆積 upper。始終維持 lower 的所有值不 大於 upper，並讓 lower 的大小等於 upper 或多一。插入時先放進 lower，再把 lower 最大值 移到 upper，修復左右順序；若 upper 變大，再把它的最小值移回 lower，恢復大小不變量。奇數個 元素時中位數是 lower 頂端，偶數個元素時是兩個頂端的平均數。插入做固定次數的 heap 操作，所以是 O(log n)；查詢 O(1)，空間 O(n)。」

分步深入解答

第一步：比較基礎方案，確認瓶頸。

二分搜尋能在 O(log n) 找到排序陣列的插入位置，卻無法消除陣列搬移成本。一般平衡樹能維持順序，但若 節點沒有子樹大小，就不能直接找到第 k 個元素。兩個 heap 只維護中位數所需的兩個邊界，因此是目前契約 下最小且完整的結構。

第二步：把中位數改寫成兩個 heap 頂端。

令 lower 保存排序後較小的一半，使用最大堆積，使其中最大值一直位於頂端；upper 保存較大的一半， 使用最小堆積，使其中最小值位於頂端。規定 lower 可以比 upper 多一個元素：

元素總數為奇數：lower 比 upper 多 1，中位數 = max(lower)
元素總數為偶數：兩個 heap 一樣大，中位數 = (max(lower) + min(upper)) / 2

Python 常見版本的 heapq 介面以最小 heap 為主。為了相容常見 Python 版本，程式將 lower 的值取負數 保存：邏輯最大值 x 對應陣列中的最小負數 -x，所以 -lower[0] 是較小一半的最大值。

第三步：使用固定的「放入、跨 heap、再平衡」順序。

與其為「新值屬於左邊或右邊」寫多組分支，可以固定執行：

1. 把 num 取負後壓入 lower。
2. 彈出 lower 的邏輯最大值，放入 upper。
3. 若 upper 比 lower 大，把 upper 的最小值移回 lower。

import heapq


class MedianFinder:
    def __init__(self) -> None:
        self.lower = []  # 以負數模擬最大堆積，保存較小的一半
        self.upper = []  # 最小堆積，保存較大的一半

    def add_num(self, num: int) -> None:
        heapq.heappush(self.lower, -num)

        largest_lower = -heapq.heappop(self.lower)
        heapq.heappush(self.upper, largest_lower)

        if len(self.upper) > len(self.lower):
            smallest_upper = heapq.heappop(self.upper)
            heapq.heappush(self.lower, -smallest_upper)

    def find_median(self) -> float:
        if not self.lower:
            raise ValueError("median is undefined for an empty stream")

        if len(self.lower) > len(self.upper):
            return float(-self.lower[0])

        return (-self.lower[0] + self.upper[0]) / 2.0

這個順序看似多搬一次，卻減少了容易寫錯的條件組合。也可以先比較 num 與 -lower[0]，再選擇目標 heap 並依大小搬移；兩種寫法複雜度相同。面試時應選擇自己較容易證明及檢查的版本。

第四步：證明順序不變量。

假設插入前，每個 lower 元素都不大於每個 upper 元素。把新值暫時放進 lower 後，只有新值可能位於 錯誤半區。此時彈出 lower 的最大值：

• 留在 lower 的所有值都不大於被彈出的值。
• 舊 lower 的值原本都不大於舊 upper。
• 因此把這個最大值加入 upper 後，新的 lower 仍不大於新的 upper 中任何值。

第二步後 upper 可能比 lower 多一個。若發生，移回 upper 的最小值。它不大於 upper 剩餘的每個 值，也不小於原本 lower 的最大邊界，所以左右順序仍成立。最後兩個 heap 大小相等，或 lower 多一個， 平衡不變量恢復。

初始化時兩個 heap 為空，不變量成立；每次插入都維持不變量，因此由歸納法可知，任何操作序列後的 heap 頂端都對應排序結果的中間位置。

第五步：走一次包含跨區搬移的例子。

插入 5： lower = [5]       upper = []        median = 5
插入 2： lower = [2]       upper = [5]       median = 3.5
插入 10：lower = [5, 2]    upper = [10]      median = 5
插入 4： lower = [4, 2]    upper = [5, 10]   median = 4.5

heap 內部不保證完整排序，[4, 2] 只表示頂端是 4。除錯時不能把 heap 陣列的列印結果當成排序陣列； 需要檢查的是 heap 性質、兩個頂端與跨 heap 不變量。

第六步：計算複雜度，並說明何時簡單方案更合適。

add_num 最多執行五次壓入或彈出，每次 heap 操作為 O(log n)，固定次數相加仍是 O(log n)。 find_median 讀取長度和頂端，是 O(1)。每個輸入值只存在其中一個 heap，空間為 O(n)。

如果產品只收集一批資料並在結束時求一次中位數，保存陣列後排序的版本較短，也可能有較好的連續記憶體效能； 沒必要為一次查詢維護線上結構。若值域固定為 0 到 100，長度 101 的計數陣列可讓插入降為 O(1)， 查詢掃描固定 101 個桶，在固定值域下也可視為 O(1)。

第七步：用確定案例與隨機差分收尾。

固定案例至少包括：

隨機測試每次產生一個整數，同時加入 MedianFinder 和參考陣列。參考陣列排序後直接取中間值；每次插入都 比較兩個結果，並斷言 len(lower) 只可能等於 len(upper) 或多一。慢版本不符合正式複雜度，卻是很好 的正確性 oracle。

高品質示範回答

「我先確認這是只插入的精確中位數，而且查詢不會發生在空資料流。若還要刪除視窗外元素，普通 heap 無法 直接刪除任意值，解法需要改變。

為了讓查詢是常數時間，我希望排序後中間位置的值一直暴露在資料結構頂端。我會用兩個 heap：最大堆積 lower 保存較小的一半，最小堆積 upper 保存較大的一半。維持兩個條件：lower 中所有值都不大於 upper，而且 lower 的大小等於 upper 或多一。

插入時我採用固定三步。先把新值放進 lower；再把 lower 最大值移到 upper，確保左右分區正確； 若 upper 變得更大，就把它的最小值移回 lower。每次結束後兩個不變量都會恢復。奇數長度時 lower 多一個，中位數就是它的頂端；偶數長度時取兩個頂端的平均數。

每次插入只有固定次數的 heap 操作，所以是 O(log n)；查詢只讀頂端，是 O(1)；所有數字仍需保存， 空間是 O(n)。我會測試單一元素、偶數、重複值、負數、單調序列與整數極值，再與每次排序的慢版本做 隨機差分。若所有資料都在 0 到 100，我會改用 101 個計數桶；若只在最後查一次，直接排序更簡單。」

常見錯誤

• 只讓兩個 heap 大小接近 → 左右值可能交錯，頂端不是兩個中間值 → 同時維護跨 heap 順序與大小不變量。
• 把較小一半放進最小堆積 → 頂端暴露全域最小值，不是左半區最大值 → 較小一半使用最大堆積。
• 偶數長度只回傳一個頂端 → 中位數定義錯誤 → 大小相等時取兩個頂端的平均數。
• 平均前用固定寬度整數相加 → 兩個大整數可能先溢位 → 先提升到更寬或浮點型別再相加。
• 認為二分插入排序陣列是 O(log n) → 找位置雖快，搬移元素仍是 O(n) → 分開計算搜尋與寫入成本。
• 把 Python heap 的底層陣列當成完整排序 → 測試會得到錯誤結論 → 只依賴頂端與父子 heap 性質。
• 對空 heap 直接讀索引 0 → 執行時錯誤位置不清楚 → 明確禁止空查詢，或在介面邊界回傳 optional。
• 宣稱線上演算法只用常數空間 → 兩個 heap 仍保存全部輸入 → 精確中位數空間為 O(n)。
• 滑動視窗仍使用相同程式 → 過期元素可能留在頂端污染結果 → 加入延遲刪除與有效大小，或改用有序多重集合。
• 只測試一個範例 → 取反、重複值與再平衡錯誤可能沒被觸發 → 固定邊界案例加隨機差分。

追問與應對

追問一：如果所有整數都在 0 到 100 之間，如何最佳化？

維護長度 101 的計數陣列與總元素數。插入只增加一個桶，時間 O(1)；查詢依兩個中間排名由小到大掃描 101 個桶，固定值域下時間及空間都可視為 O(1)。若值域上限會隨輸入成長，掃描成本應寫成 O(R)， 其中 R 是值域大小，不能繼續稱為常數。

追問二：如果 99% 的值在 0 到 100，其他值可能任意大呢？

可以替區間內保留 101 個計數桶，並分別用支援排名選擇的有序結構保存小於 0 與大於 100 的例外值。查詢時 先依例外值數量判斷目標排名位於左例外區、固定區間或右例外區，再到對應結構選擇。若只有普通 heap 而沒有 排名能力，不能因為「99% 在範圍內」便宣稱查詢為常數時間；極端情況下中位排名仍可能落在例外值結構。

追問三：如何求最近 k 個數字的滑動視窗中位數？

視窗滑動時要刪除離開的值。二元 heap 無法有效率地定位任意元素，常見做法是兩個 heap 加延遲刪除表： 邏輯刪除時記錄次數並更新兩個 heap 的有效大小，只有待刪除值到達頂端時才真正彈出；每次讀中位數前清理 兩個頂端。更新為攤銷 O(log k)，查詢頂端仍是 O(1)。支援重複值與刪除的平衡多重集合更直接，但 依賴語言函式庫。

追問四：無界資料流且記憶體固定，還能回傳精確中位數嗎？

對任意整數資料流，一般無法在固定記憶體中永遠保留精確中位數，因為被丟棄的歷史值可能在未來決定中間排名。 需要把契約改成近似分位數，使用有誤差界的分位數摘要，並明確指定允許的排名誤差、信賴要求與合併方式。 此時答案已不是精確的兩個 heap。

追問五：如何支援多個執行緒同時插入及查詢？

兩個 heap 構成一個邏輯狀態。最簡單的正確做法是在完整的 add_num 和 find_median 外使用同一把互斥鎖， 避免查詢看到「已從 lower 彈出、尚未放進 upper」的中間狀態。若讀取流量很高，可以發布不可變的 中位數快照，但快照更新頻率會帶來新鮮度取捨，必須寫入介面契約。

追問六：多個分片各自給出中位數，能直接合併成全域中位數嗎？

不能。分片中位數遺失了分片大小與分布資訊；即使取加權平均，也不等於全域中位數。精確結果需要能回答全域 排名的結構，例如依值域彙總計數後做分散式選擇；近似結果則使用可合併的分位數摘要。先確定精度與延遲目標， 再選擇全域結構。