作者LPH66 (ha(ruhi|yate)ism)
看板CSSE
標題Re: [問題] heap tree
時間Sat May 26 05:28:26 2007
※ 引述《akdsy (我很想妳)》之銘言:
: 不知道在這裡問對不對!
: 關於 max-heap !
: 要是給定一個數列,
: 求max-heap
: 法一) (根據我學過的方法)
: 先建完一個almost complete binary tree 之後,
: (就是由root向下把數列裡的值,按順序一個一個填進去 binary tree裡)
: 再由最下面的以bottom-up的方式,
: 把大的擺上去,
: 小的放下來,
: 最終每個父節點都大於其子孫,(這樣講前輩懂我的意思嗎?)
: 法二) (.....聽說是參考答案)
: 每建一個node就以bottom-up的方式作heap,
: (跟法一最大的不同,就是他邊建樹邊heap.....)
: 等到所有node都建完之後,
: 也就是答案。
: 以上!
: 請問哪一個方法是對的呢?
: 因為其結果不同,
: 所以讓我困惑很久!
: 感謝您的解惑!
都對
法一較適用於將一個已經有值的陣列建成heap
法二較適用於一個一個加入的建立
你的問題關鍵點在相同的元素排成的heap也會有所不同
例如1~7 可以有這些種max heap:
7 7 7
/ \ / \ / \
5 6 3 6 6 5 等等
/ \ / \ / \ / \ / \ / \
1 2 3 4 1 2 4 5 3 2 4 1
每一個都是正確的max heap 儘管排法有所不同
--
"LPH" is for "Let Program Heal us"....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 192.192.197.115
推 akdsy:這樣說的話,要是題目給定一個數列,那法一是較好的作法呢? 05/26 09:27
→ akdsy:感謝您的熱情相助!!! 05/26 09:29
推 AppleFox:通常都是用第一個方法吧 BTW 從n/2開始建heap就好了 05/29 23:09
推 akalashnikov:這是 Binary Heap 的做法,還有 Binomial, Fibonacci 05/31 09:28