[理工] 資結 調整max heap的演算法問題

作者: allenpong (阿倫)   2022-11-23 02:26:17
https://i.imgur.com/VzeIzuP.jpg
https://i.imgur.com/cgkUI51.jpg
如圖,為甚麼要加一個k=tree[i].key
tree[i]本身不就是節點值了嗎
而且後面tree[j/2]=tree[j]又沒加key了
整個超怪,而且我看板上之前的講義都沒有這個.key
所以其實可以不用加對吧?
跪求大大回覆,500p奉上,想了一個
晚上= =
作者: mathtsai (mathtsai)   2022-11-23 17:53:00
雖然不知道這是什麼語言但是tree[j]指的應該是該nodetree[j].key位該node存的key值
作者: allenpong (阿倫)   2022-11-23 18:01:00
是pascal語法,意思是大大說的那樣沒錯,所以說tree[i]是node的位址嗎 ,可是這樣為甚麼tree[j/2]=tree[j]不用加.key,不是要把兒子的值給爸爸嗎,沒加是變成兒子的位址給爸爸?
作者: mathtsai (mathtsai)   2022-11-23 18:07:00
把裡面的值換掉就可以了另外j/2不就是i嗎?
作者: allenpong (阿倫)   2022-11-23 18:12:00
是i沒錯,不好意思,把裡面的值換掉具體來說是甚麼意思
作者: mathtsai (mathtsai)   2022-11-23 18:12:00
他這樣寫就是把node交換,實際上把裡面的值交換就可以
作者: allenpong (阿倫)   2022-11-23 18:13:00
喔 我懂了太感謝大大了XD
作者: mathtsai (mathtsai)   2022-11-23 18:19:00
喔 說錯了 j/2不一定是i因為他沒去更新i的值 更正一下可以去看CLRS裡面heapify是怎麼做的比較好懂
作者: allenpong (阿倫)   2022-11-23 18:27:00
應該說第一次j/2是i 做第二次就是j的父點(j會往下鑽好的 我去研究看看 感恩
作者: password5353 (阿宅)   2022-11-28 16:12:00
tree[i]應該是指index tree[i].key是index中的值我的理解是這樣

Links booklink

Contact Us: admin [ a t ] ucptt.com