為一個 Completed B.T 且 root 為空,則滿足以下 3 個 path
p1. 左兄 ≤ 右兄
p2. 令 X 為某點,若此點有祖父,則祖父的左子點必須 ≤ X
p3. 令 X 為某點,若此點有祖父,則祖父的右子點必須 ≥ X
即代表整個 heap root 的左子為 min、右子為 max
可以看到上圖的點 40,其有祖父(root),則祖父的左子點 (5) 會小於 40、右子點 (75) 會大於 40
先放置到 Last node 下一個
check p1
check p2 調整至 SMMH
check p3 調整至 SMMH
不一定只調整一次
以插入 90 為例,由於他沒有右兄,所以不用換位置,然而其祖父之右子點 (40) 比起 90 還小,因此做第一回合交換
交換後發現其祖父之右子點 (75) 比起 90 還小,因此做第二回合交換
欲刪除 5,將 last node 40 放入 root 之左子,由於左兄比右兄小,因此 p1 不用調整,當檢查 p2,發現 8 是要調整之最小點,予以交換
欲刪除 90,將 last node 60 放入 root 之右子,由於左兄比右兄小,因此 p1 不用調整,當檢查 p3,發現 75 是要調整之最大點,予以交換