推 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
※ 引述《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