[理工] 資結-Heap in descending order

[ssssIssss (O_O)]

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?
但又如這題

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?
推 yorunohoshi: 用heap sort的話 build heap→heap sort→然後用個
→ yorunohoshi: stack反序輸出再建一個heap 可以O(nlogn)
→ Gabino: 其實用max heap做heap sort出來應該就ascending order了？
→ yupog2003: max heap做heap sort應該是descending order?
→ yupog2003: min heap做heap sort是ascending order?
推 Transfat: max heap做heap sort應該是ascending order
→ Transfat: 如果是用array存放element,他是把Root和the last node互
→ Transfat: 換位置，root最大，換到最後一個位置，所以最後sort完會
→ Transfat: 是ascending order
→ Transfat: 題目解答應該是用top-down建heap
→ yupog2003: 喔喔對我想錯了，T大跟G大才是正確的
所以要求出ascending是由heap sort完的tree而來

而我發問的題目，其實是要問如何建heap？因此先用top-down建出的樹，而之後要descen
ding則再做sort..?
※ 編輯: ssssIssss (140.112.94.109), 01/31/2017 10:08:24