演算法圖鑑
資料結構 · 3 個細項

Heap / Priority Queue堆積

堆積是一棵用陣列存的完全二元樹,父節點永遠比子節點小(或大)。它不排序全部資料,只保證頂端是極值,所以插入與取出都是對數時間,是優先佇列的標準實作。

為什麼要學 Heap / Priority Queue

現實中的應用
作業系統的工作排程

高優先度的程序先跑,新程序隨時加入。優先佇列讓「加入」和「取最高優先」都很快,Linux 的 CFS 用的是類似結構。

→ 對應課程:Binary Heap
熱門文章 Top 10

一千萬篇文章要取閱讀數前十,不用全部排序。維持一個大小為 10 的最小堆積,掃一遍就好。

→ 對應課程:Top-K Problems
即時中位數

資料流不斷進來,隨時要報中位數。一個最大堆積管左半、一個最小堆積管右半,中位數永遠在兩個頂端。

→ 對應課程:Two Heaps

細項

3