Re: [問題] Max Heap Tree
※ 引述《senglish86 (kururu)》之銘言：
: 開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
: Visual Studio C
: 問題(Question)：
: 想用array做出符合Max Heap Tree的陣列 但好像有問題
: 餵入的資料(Input)：
: 3 5 2 6 1
: 預期的正確結果(Expected Output)：
: 6 5 2 3 1
: 錯誤結果(Wrong Output)：
: 6 5 2 1 3
: 程式碼(Code)：(請善用置底文網頁, 記得排版)
: http://ideone.com/dFjZJ
: 補充說明(Supplement)：
: 有人說我不需要執行creatheap這個副程式
: 我不太確定
: 請各位強者幫忙 謝謝
http://ideone.com/nOSgF
你的這個程式最大的問題在：沒有弄懂 Max Heap 的特性。
MaxHeap 特性有 2。
1. 是 MaxTree: 每個 node 的值會大於其任一 children 值。
2. 是 Complete Binary Tree: 與 Full Binary Tree 所用的相對位置相同。
例：
1
2 3 高度為 3 的 Full Binary Tree.
4 5 6 7
1
2 3 高度為 3，node 數為 4 的 Complete Binary Tree.
4
根據第 2 點，Max Heap 適合用 array 儲存，因不會浪費多餘空間。
而 MaxHeap 的操作有個重點是它在任何時候都要符合以上的情況，
所以我看你的程式每次 insert 時都要重新 createHeap，
這個是不需要的，
而且也不需要從 number[] 搬到 heap[] 再搬回 number[]，
在 number[] 中做完即可。
你一次讀完 5 個數字後，
要一個一個弄進 MaxHeap 中，
所以我用一個迴圈依序將 number[1] ~ number[5] 數字 insert 進去。
insert 時跟其 parent 做比較，若比 parent 大就將 parent 值放進現有位置。
最後講一下，
因為是一路往上比，所以可以等比完後再將新值直接放入新的位置，
不必一直 SWAP，這樣較節省時間 (node 數多時)，
因為一個 SWAP 要做三次指定值的動作。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.209.4
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：