堆積
此條目需要補充更多來源。 (2024年8月11日) |
堆(Heap)是計算機科學中的一種特別的完全二叉樹。若是滿足以下特性,即可稱為堆積:「給定堆積中任意節點P和C,若P是C的母節點,那麼P的值會小於等於(或大於等於)C的值」。若母節點的值恆小於等於子節點的值,此堆積稱為最小堆積(min heap);反之,若母節點的值恆大於等於子節點的值,此堆積稱為最大堆積(max heap)。在堆積中最頂端的那一個節點,稱作根節點(root node),根節點本身沒有母節點(parent node)。
「堆積」的各地常用名稱 | |
---|---|
中國大陸 | 堆 |
臺灣 | 堆積 |
堆積始於J. W. J. Williams在1964年發表的堆積排序(heap sort),當時他提出了二元堆積樹作為此演算法的資料結構。
性質
堆的實現通過構造二叉堆(binary heap),實為二叉樹的一種;由於其應用的普遍性,當不加限定時,均指該數據結構的這種實現。這種數據結構具有以下性質。
- 任意節點小於(或大於)它的所有後裔,最小元(或最大元)在堆的根上(堆序性)。
- 堆總是一棵完全樹。即除了最底層,其他層的節點都被元素填滿,且最底層儘可能地從左到右填入。
將根節點最大的堆叫做最大堆或大根堆,根節點最小的堆叫做最小堆或小根堆。
支持的基本操作
操作 | 描述 | 時間複雜度 |
---|---|---|
build | 採用羅伯特·弗洛伊德提出的較快方式建立堆 | |
insert | 向堆中插入一個新元素 | |
update | 將新元素提升使其符合堆的性質 | |
get | 獲取當前堆頂元素的值 | |
delete | 刪除堆頂元素 | |
heapify | 使刪除堆頂元素的堆再次成為堆 |
某些堆實現還支持其他的一些操作,如斐波那契堆支持檢查一個堆中是否存在某個元素。
示例代碼
為將元素X插入堆中,找到空閒位置,建立一個空穴,若滿足堆序性(英文:heap order),則插入完成;否則將父節點元素裝入空穴,刪除該父節點元素,完成空穴上移。直至滿足堆序性。這種策略叫做上濾(percolate up)。[1]
以上是插入到一個二叉堆的過程。
DeleteMin
,刪除最小元,即二叉樹的根或父節點。刪除該節點元素後,隊列最後一個元素必須移動到堆得某個位置,使得堆仍然滿足堆序性質。這種向下替換元素的過程叫作下濾。
應用
堆排序
堆(通常是二叉堆)常用於排序。這種算法稱作堆排序。
事件模擬
主要運用堆的排序以選擇優先。
優先權佇列
在隊列中,調度程序反覆提取隊列中第一個作業並運行,因為實際情況中某些時間較短的任務將等待很長時間才能結束,或者某些不短小,但具有重要性的作業,同樣應當具有優先權。堆即為解決此類問題設計的最佳數據結構。[1]