[理工] 資結-Heap in descending order

看板Grad-ProbAsk作者 (O_O)時間9年前 (2017/01/30 11:58), 9年前編輯推噓2(2推 0噓 11→)
留言13則, 4人參與, 最新討論串1/1
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
→
01/30 12:02, , 1F
max heap?
01/30 12:02, 1F
但又如這題 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
→
01/30 12:47, , 2F
第3小題應該是用heap sort 排完變成ascending order?
01/30 12:47, 2F
推
01/30 12:52, , 3F
用heap sort的話 build heap→heap sort→然後用個
01/30 12:52, 3F
→
01/30 12:52, , 4F
stack反序輸出再建一個heap 可以O(nlogn)
01/30 12:52, 4F
→
01/30 13:00, , 5F
其實用max heap做heap sort出來應該就ascending order了？
01/30 13:00, 5F
→
01/30 13:22, , 6F
max heap做heap sort應該是descending order?
01/30 13:22, 6F
→
01/30 13:22, , 7F
min heap做heap sort是ascending order?
01/30 13:22, 7F
推
01/30 14:02, , 8F
max heap做heap sort應該是ascending order
01/30 14:02, 8F
→
01/30 14:03, , 9F
如果是用array存放element,他是把Root和the last node互
01/30 14:03, 9F
→
01/30 14:03, , 10F
換位置，root最大，換到最後一個位置，所以最後sort完會
01/30 14:03, 10F
→
01/30 14:03, , 11F
是ascending order
01/30 14:03, 11F
→
01/30 14:04, , 12F
題目解答應該是用top-down建heap
01/30 14:04, 12F
→
01/30 15:11, , 13F
喔喔對我想錯了，T大跟G大才是正確的
01/30 15:11, 13F
所以要求出ascending是由heap sort完的tree而來 而我發問的題目，其實是要問如何建heap？因此先用top-down建出的樹，而之後要descen ding則再做sort..? ※ 編輯: ssssIssss (140.112.94.109), 01/31/2017 10:08:24
‣ 更多 ssssIssss 的文章
文章代碼(AID): #1OZhdt4D (Grad-ProbAsk)