堆積 (Heap)

完全二元樹實現的優先佇列資料結構

堆積的定義與性質

堆積是一種特殊的完全二元樹,滿足堆積性質:每個節點的值都大於等於(最大堆積)或小於等於(最小堆積)其子節點的值。

基本操作

插入 (push):新增元素放到尾部,向上調整 (bubble up),時間 O(log n)。

刪除 (pop):移除根節點,將尾部元素移到根,向下調整 (bubble down),時間 O(log n)。

建堆 (heapify):從最後一個非葉節點開始向下調整,時間 O(n)。

堆積排序

利用最大堆積進行排序:先將陣列建堆,然後重複取出根節點(最大值)放到陣列末尾,時間 O(n log n),空間 O(1)。與快速排序相比,堆積排序保證最壞情況也是 O(n log n)。

優先佇列

堆積是實現優先佇列最常見的方式。優先佇列中的每個元素有優先級,每次取出優先級最高的元素。應用包括:任務排程、Dijkstra 最短路徑、Huffman 編碼。

本課程範例

相關連結