[理工] [資結]-台大99-軟體設計-d heap

作者EntHeEnd (...)

看板Grad-ProbAsk

標題[理工] [資結]-台大99-軟體設計-d heap

時間Fri Mar 5 20:13:32 2010

http://www.lib.ntu.edu.tw/exam/graduate/99/99405.pdf 請問第三題 d heap 要怎樣heapify呢類似 binary heap 從最後一個parent=floor(最後一個child的index/d)開始往回調整每次都選children中最大的和parent交換一直調整到root 每次交換如果造成subtree不滿足d heap性質subtree也要調整(遞迴) 這樣嗎 ? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.126.125.176

推 polomoss:這題20分我沒寫.....看到很傷心 03/05 20:14

→ EntHeEnd:現在會了嗎 XD... 03/05 20:21

推 lightergogo:這題是我覺得最好寫得一題XD 03/05 20:24

→ EntHeEnd:怎樣寫能不能回一下文 ? 03/05 20:26

推 lightergogo:就你寫的這樣, 跟binary heap 一樣 03/05 20:29

→ devilend:只要跟parent比較就好了吧..跟binary heap一樣.. 03/05 20:29

→ EntHeEnd:orz... 這樣感覺有寫和沒寫一樣 03/05 20:30

※ 編輯: EntHeEnd 來自: 59.126.125.176 (03/05 20:31)

→ EntHeEnd:改一下弄錯 03/05 20:31

→ EntHeEnd:對了第一題只能用暴力法 bottom up嗎 ? 03/05 20:46

推 chenbojyh:第一題我是用bottom up 03/05 21:43

→ EntHeEnd:hmm... 03/05 22:05

推 jtruby:有說一定要 bottom up 嗎??? 03/05 22:15

→ EntHeEnd:樓上有其他有效率的做法可以提供嗎 ? 03/06 08:41

推 Lautreamont:第一題不是可以用遞迴嗎? 03/06 19:22