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

[allenpong (阿倫)]

 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奉上，想了一個
晚上= =
----
Sent from BePTT on my iPhone 11 Pro

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.94.203 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1669141579.A.39A.html
※ 編輯: allenpong (1.161.94.203 臺灣), 11/23/2022 02:45:01
→ mathtsai: 雖然不知道這是什麼語言
→ mathtsai: 但是tree[j]指的應該是該node
→ mathtsai: tree[j].key位該node存的key值
→ allenpong: 是pascal語法，意思是大大說的那樣沒錯，所以說tree[i]
→ allenpong: 是node的位址嗎 ，可是這樣為甚麼tree[j/2]=tree[j]不
→ allenpong: 用加.key，不是要把兒子的值給爸爸嗎，沒加是變成兒子
→ allenpong: 的位址給爸爸？
→ mathtsai: 把裡面的值換掉就可以了
→ mathtsai: 另外j/2不就是i嗎？
→ allenpong: 是i沒錯，不好意思，把裡面的值換掉具體來說是甚麼意思
→ mathtsai: 他這樣寫就是把node交換，實際上把裡面的值交換就可以
→ allenpong: 喔 我懂了
→ allenpong: 太感謝大大了XD
→ mathtsai: 喔 說錯了 j/2不一定是i
→ mathtsai: 因為他沒去更新i的值 更正一下
→ mathtsai: 可以去看CLRS裡面heapify是怎麼做的
→ mathtsai: 比較好懂
→ allenpong: 應該說第一次j/2是i 做第二次就是j的父點(j會往下鑽
→ allenpong: 好的 我去研究看看 感恩
推 password5353: tree[i]應該是指index tree[i].key是index中的值
→ password5353: 我的理解是這樣