Heap 總整理
Fibonacci Heap
| Actual | Amortize | |
|---|---|---|
| Insert | O(1) | O(1) |
| Delete min | O(n) | O(logn) |
| Meld | O(1) | O(1) |
| Delete 'any' | O(n) | O(logn) |
| Decrease key | O(1) | O(1) |
insert
insert 當作一個新節點 並合併
delete
Min-Max-heap
- 完美二元樹
- root 一定要是min
- 接下來每一層按照min -> max -> min -> max...
insert
先跟父節點比 接下來都跟grand parent比 直到到root
delete
最後一個節點頂替root 找grand childs最小的交換 交換完後還需要跟父節點比
Deap (Doubly ended Heap)
- 完美二元樹
- Root 是空的
- 左邊的是min heap 右邊的是max heap
- 如果沒有對應的node 就找那個node 的 parent
| Actual | |
|---|---|
| Insert | O(logn) |
| Delete min | O(logn) |
insert
先跟對應的找 比較大的放右邊 比較小的放左邊 接下來各自檢查heap是否合法
delete Min
刪除之後找左右child最小的替代並且往上替補直到到leaf，最後再執行insert(最後一個節點,空缺位置)
SMMH (Symmetric min-max heap)
- 完美二元樹
- root 空的
- 左兄弟 <= 右兄弟
對於一個節點i i的左子點是左子樹的最小值 i 的右子點是子樹的最大值
| Actual | |
|---|---|
| Insert | O(logn) |
| Delete min | O(logn) |
insert
放在最後一個節點 左兄弟沒有<=右兄弟 先對調 檢查上一層的兩個節點 如果沒有符合小於左邊節點或大於右邊節點就對調
delete min
刪除root的左邊節點 拿最後的一個node來補 接下來先檢查左兄弟沒有<=右兄弟 先對調 再往下檢查去比較左節點與右子樹的左節點 比較小做對調 每次下去檢查都要去檢查左兄弟沒有<=右兄弟