為什麼這篇Heap Sort鄉民發文收入到精華區：因為在Heap Sort這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者ssssIssss (O_O)看板Grad-ProbAsk標題[理工] 資結-Heap in d...
http://i.imgur.com/HalteAX.jpg
如圖，此題第一小題要求建一個Heap滿足can output the data in descending order
這樣要怎麼建呢@@
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.94.109
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485748727.A.10D.html
→ yupog2003: max heap?01/30 12:02
但又如這題
http://i.imgur.com/VCMN79V.jpg
第三小題要write out the result of ascending heap
http://i.imgur.com/PRcsXa7.jpg
解答如上圖，剛好第二小題是min heap可以對照，感覺兩者不太相同..?
抱歉筆記超級亂m(_ _)m
※ 編輯: ssssIssss (140.112.94.109), 01/30/2017 12:24:43
→ Gabino: 第3小題應該是用heap sort 排完變成ascending order?01/30 12:47
推 yorunohoshi: 用heap sort的話 build heap→heap sort→然後用個 01/30 12:52
→ yorunohoshi: stack反序輸出再建一個heap 可以O(nlogn)01/30 12:52
→ Gabino: 其實用max heap做heap sort出來應該就ascending order了？01/30 13:00
→ yupog2003: max heap做heap sort應該是descending order?01/30 13:22
→ yupog2003: min heap做heap sort是ascending order?01/30 13:22
推 Transfat: max heap做heap sort應該是ascending order01/30 14:02
→ Transfat: 如果是用array存放element,他是把Root和the last node互 01/30 14:03
→ Transfat: 換位置，root最大，換到最後一個位置，所以最後sort完會 01/30 14:03
→ Transfat: 是ascending order01/30 14:03
→ Transfat: 題目解答應該是用top-down建heap01/30 14:04
→ yupog2003: 喔喔對我想錯了，T大跟G大才是正確的01/30 15:11
所以要求出ascending是由heap sort完的tree而來
而我發問的題目，其實是要問如何建heap？因此先用top-down建出的樹，而之後要descen
ding則再做sort..?
※ 編輯: ssssIssss (140.112.94.109), 01/31/2017 10:08:24