概念地圖・費氏堆
作者 山姆（謝冠生）・喵喵書評創辦人
發布
分類：系統
這一頁不只是把一個概念解釋一遍——一張自己畫的結構圖，加上拿台灣情境從頭走一次的實例演練、這個框架什麼時候會騙你，以及它接回 P.A.I.N. 之後長什麼樣。一頁必須交付的三層 →
費氏堆：進來時不排序，要拿才整理
一批東西進來，你是當場把它插進正確的位置，還是先丟在門口那一排、等真的要拿的時候再整理一次？費氏堆選的是後面那條路。它把一堆小樹散著擺，手上只維護一個指標，記住現在最小的那一棵在哪裡；新東西進來、有人臨時插隊，都只動門口那一排，幾乎不花力氣。真正的整理集中在一個時刻——你伸手要拿最小的那一次，這時才把門口併成有序的幾排，帳一次付清。這張圖畫的就是那片森林：誰站在門口、誰身上掛著記號、記號滿了會發生什麼事。
七個零件，各自在管什麼
整張圖只有一條帶子、幾棵樹、一個小方塊。把它們拆開來，各自負責的事情很不一樣。
| 零件 | 圖上長什麼樣 | 它在管什麼 |
|---|---|---|
| 根串列 | 上方那條淡金色橫帶，四個圓圈並排 | 新進來的、被剪下來的，一律先丟這裡，彼此之間不排順序 |
| 每一棵樹 | 帶子底下往下長的節點，每一棵的層數不一樣 | 已經整理過的一小段順序，上面那顆一定比底下的小 |
| 最小指標 | 左邊箭頭指著的那個圈，外面多一道環 | 隨時知道最小的在哪，不必掃過整片森林 |
| 降鍵 | 朱紅虛線箭頭往上折回帶子 | 某一個節點忽然變急，把它從樹上剪下來，直接丟到門口 |
| 記號 | 節點右上角那個朱紅小方塊 | 這一組已經被抽走過一個，狀態記在身上，不會忘 |
| 級聯剪枝 | 第二支朱紅箭頭，從掛記號的節點出發 | 記號滿了就跟著上去，避免樹被抽成沒幾個人的空架子 |
| 合併 | 最下方那一格「要拿最急那一台」 | 只在取最小的那一刻做一次，把門口那排併成有序的幾排 |
這張表讀出來的言外之意是：便宜的動作都被推到門口那條帶子上，貴的動作只有一個，而且你可以決定它什麼時候發生。記號那一列是唯一一個「你不出手、它自己會發生」的機制——它在替後面那次合併控制成本。
換成這種堆法之前，先過這四關
一、進來的多，還是拿走的多。費氏堆把力氣全部押在「插入便宜」上。如果你的工作量是進來十件、拿走十件，這筆交易沒什麼賺頭；要拉開差距，得是進來一百件、真正被拿走的只有幾件。自問：這個月新增了幾件，實際被處理掉的又是幾件？
二、插隊發生得多不多。「有人臨時把某一件往前調」在這裡是頭等公民，剪一刀就好，不必重排整排。這件事在你這行若一個月發生兩次，等於用不到它最強的那一手。自問：上一個月排定之後又被調前的，有幾件？
三、最小的那一件，你幾秒答得出來。整套結構的價值，最後濃縮成一個指標。要是你現在得翻三份表、問兩個人才知道哪件最急，那個指標其實不存在，而它是這片森林裡唯一不能省的東西。自問：此刻最急的是哪一件，我不看電腦答不答得出來？
四、被抽空的那一組，你有沒有規矩。記號那條規則看起來很枝微末節，卻是整個成本估算的支點。沒有它，某一組會被一件一件抽到只剩空殼，而下一次合併照樣得把那個空殼算進去。自問：一組東西被抽走第二件時，剩下的會怎麼處理，寫下來了嗎？
一家彰化農機行的院子，一個收割季走一遍
底下這家台灣中部的農機行，是為了把這個結構講清楚而編出來的示意情境，沒有指涉任何真實公司。
- 推進院子：收割季前兩週，二十三台待修機具陸續推進來。登記一台四十秒，只寫車號跟「幾天後要下田」。兩週的登記加起來約十五分鐘
- 不排順序：誰擺在院子哪一格沒有規則。白板上只寫一行——現在最急：三號機，兩天後下田。「先修哪一台」看那一行就有答案
- 開工那一刻：師傅早上七點進場，這時才把二十三台按工時級距兩兩併排，整理成五排，花掉十二分鐘。整批的帳，集中在這一次付
- 電話插隊：上午六通電話要改急件，六台各自從原本那排抽出來，直接推到門口。抽出來就好，不必動那一排的其他人
- 抽第二次：第六通抽的，是今天已經被抽走過一台的那一排。那排剩下的機器跟著整排推到門口。門口從五個排頭變成十二個
- 下一次開工：十二個排頭要再併一次，八分鐘。插隊省下來的力氣，會在下一次合併時回頭收
把兩種做法的帳並排看。進來就當場排進正確位置：一台平均要跟現有的比五次、一次三十秒，一台兩分半，二十三台是五十七分半。先堆著、開工那一刻再併一次：登記十五分鐘加上合併十二分鐘，二十七分鐘。省下來的那半小時來自一個安排：整理被延後到「真的需要順序」的那一刻，而且只做一次。真正要盯的是後半段——六通插隊電話沒有讓任何一排重排，帳記在別的地方：門口那排被撐成十二個，下一次合併多花八分鐘。記號那條規矩就是為了讓這筆帳不會滾大：一排被抽第二次，整排上去重排，免得院子裡站著一堆掛著五層、實際只剩三台的空架子。以上為說明結構用的示意情境，僅供理解框架之用。
這片森林什麼時候會騙你
- 它保證的只有一件事：一整串動作加起來的總帳。「平均起來很便宜」的說法，前提是你願意讓某一次特別貴——那一次就是伸手拿最小的時候，整批合併的帳全部落在它頭上。如果你的系統真正怕的是「最壞那一次要等多久」，像急診分流、產線的即時控制、有服務水準罰則的派工，把帳集中起來反而是壞消息。這種場合要的是每一次都平穩，寧可平常慢一點。
- 量小的時候，複雜度自己會吃掉好處。每個節點要多記父親、階數、記號三樣東西，實作的細節也多，出錯的地方跟著多。資料只有幾百筆時，一個結構簡單的二元堆多半跑得比它快——省下來的理論成本，還不夠付多出來的那些簿記。真正值得換的時機很窄：量大，而且插隊次數遠遠多於取出次數。
- 「先堆著」很容易被讀成「不用整理」。這套堆法的省，完全建立在兩件事真的有做：取最小那一刻把門口確實併乾淨，以及記號規則確實執行。少了任何一個，門口那排只會愈長愈長，某一天你伸手拿東西，一次付掉的是好幾天累積下來的帳。它從來沒有讓整理消失，只是讓你挑時間。
用痛點的眼光看那面白板
白板上那一行字，是整個院子裡唯一有順序的地方。
費氏堆把力氣省在對的位置：不必要的排序全部延後，力氣留給真的要拿東西的那一刻。可是排序用的那個數字，是誰給的？在院子裡它叫「幾天後要下田」，聽起來夠客觀了——直到你發現有位客戶三通電話都沒打，他的機器就這樣一直躺在第二排。這張圖畫得出哪一台最急，畫不出哪一位客戶已經在心裡把你換掉。會打電話的人永遠有辦法把自己的數字調小；安靜的那一位不會抗議，他只會在下一季換一家修。P.A.I.N. 那把尺量的正是後面這件事——誰在痛、痛卡在哪個環節、他忍了多久、忍不住的時候會做什麼。這四個問題，一個都不在節點的鍵值裡。今晚可以做的小動作：把急件清單翻過來，圈出這一季一通電話都沒打過的三個名字，明天早上主動撥回去。
常被問到的幾件事
費氏堆跟一般的二元堆，差別到底在哪？
差別在整理的時機。二元堆每插進一個元素，就當場把它往上換到正確的位置，順序隨時是對的；費氏堆讓新元素躺在根串列上，整片森林平常是散的，只有取出最小的那一刻才做一次合併。所以二元堆的每一次都差不多快，費氏堆是平常極快、偶爾一次很慢。真正拉開差距的動作是「降鍵」——把某個元素的鍵值調小，二元堆得往上換好幾層，費氏堆剪一刀丟到門口就結束。
「攤還」是什麼意思，跟平均一樣嗎？
不完全一樣。平均是把實際發生的次數加起來除，攤還則是先替每個便宜動作多收一點「押金」，存起來付給將來那次昂貴的合併。用院子的話講：登記每一台時都當作多花了幾秒，這些幾秒攢著，就是開工那天十二分鐘的來源。所以攤還保證的是「一整串動作加起來不會超過多少」，它從頭到尾都沒有承諾單獨某一次會很快。
記號那條規則不做會怎樣？
會慢慢崩。記號的用意是不讓任何一棵樹被抽到「掛著很多層、底下卻沒幾個人」。少了它，被抽剩的空架子會一直留在森林裡，而合併的成本是照樹的層數算的，於是你付了高層數的錢，買到的卻是幾乎空的一棵。理論上那個漂亮的成本上界，正是靠這條規則撐住的——它逼著被掏空的節點自己上去重新排隊。
什麼樣的工作真的適合這種延後整理？
三個條件同時成立時最划算：進來的量遠大於拿走的量、常常有人臨時調整優先順序、而且你有權決定「什麼時候才需要一份正確的排序」。最典型的是路徑規劃與大型排程這類跑一次算很多次的計算。反過來，客服工單、掛號、值班交接這種每一件都會被人看著等的場合，就別把帳集中起來——那一次合併發生時，等的人是活的。
同樣是把順序這件事收進結構裡，AVL 樹旋轉走的是相反那條路，它在東西放進去的那一刻就先把架子扶正，換來每一次查詢都只翻幾層。要是你排的不是機器而是專案，加權最短工作優先是另一把尺，它把「拖下去的代價」跟工期擺在一起除。
喜歡這篇文章嗎？
每週幫你拆二本好書，把判斷力、好書金句、好問題，直送你的信箱。
不適合你可隨時退訂 · 每週兩封，陪你把書讀進生活。
送出即表示同意我們依隱私權政策使用你的 email。