Introduction
堆積是一種特殊的樹狀資料結構,滿足以下性質,以下用最大堆積為例
- Parent Node 的值總是大於等於 Child Nodes 的值。
- Binary Heap 為一個完全二元樹,即除了最底層,其他層都是滿的,且最底層的節點都靠左對齊。
至於什麼是二元樹?二元樹是一種樹狀結構,其每個節點最多只能有兩個 Children。
Heap operations
堆積有以下幾種操作
- Build Heap: 將一個陣列轉換成堆積
- Insert: 插入一個新元素到堆積中
- Extract Max: 移除並回傳堆積中最大的元素
Build Heap (Heapify)
將一個陣列轉換成堆積的方法稱為 Heapify。
常見的方法是從最後一個 Parent Node 開始,將每個 Parent Node 與其 Children 比較,若 Parent Node 小於 Children,則交換兩者的值,並繼續往下比較,直到該 Parent Node 大於等於所有他的新 Children。