[理工] [資結] Min Max heap

[a613204 (胖胖)]

想請問刪除最小值的作法

當刪除最小值時 , root刪除 , 最後一個節點令為x重新插入到樹根為空的min max heap

當最小值是孫子時令為k , 若k < x 則將k置於root中 , 此時檢查 x是否大於k的父親

若大於的話則將x與k的父親交換值(變數名稱不變)

再將x重新插入到樹根為空的min max heap

這邊想請問紅色字的部份 : 是指原本以k為樹根的min max heap嗎??

是不是因為若k < x 則將k置於root中 -> 把k刪掉從原本位置刪除而放到root

因此以k為樹根的min max heap就變成樹根為空??

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 123.0.42.10
推 jackbll:yes 總之就是從被刪掉的點繼續作min max heap
→ a613204:所以這裡k點就是被刪除的點然後放在root的位置
→ a613204:然後再將x插入到原本以k點為樹根的子樹(現在k點為空)
→ a613204:應該是這樣沒錯吧@@ 抱歉想確認清楚點
→ jackbll:這....不是你上面原文的意思嗎?? XD
→ a613204:好像是耶XD 謝謝你