[理工] 105交大資演 21,28 疑問

[kyuudonut (善良老百姓)]

21. http://imgur.com/a/5eAI4

答案是 (C)

想請問 (a) 錯在哪

另外 (c) heap 的 merge 不是需要 O(n) 嗎

28. http://imgur.com/a/kqror

答案是 (C)

請問 (a) 錯在哪

謝謝

--
  ◢        ◣▂  丹丹先生，請問你對其他速食店降價          丹你老木！
           ◤_      ◢       ◣         會擔心嘛？   ▂▂▂▏╯
 |════   ⊙            ◤◤     ╯         ▁▃▃˙˙ █
 ▇▇▇▇▇▇▇█║      ◤ ●      ╭═╮         ▁◤   ▋
 █████ __ █║                 [TV]人   ◥███        ◢
    ◣▅     ◤             ▅◢◢◢◤  ◥▆▄_◥██▄▃▆◢█◣    φjeans1020

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.116.1.136
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483425674.A.BAC.html
推 Astar5566: 左傾樹的定義只有左比右深 所以skew也算
喔喔喔喔喔喔喔，原來如此，太謝謝了
※ 編輯: kyuudonut (140.116.1.136), 01/03/2017 14:49:43
推 Transfat: Leftist tree不是也是個Heap嗎？所以他不算是balanced ?
→ Transfat: 28(a) Quick Sort應該根amortized沒什麼關係
對齁！qsort 的分析並沒有用到 amortized cost orz

→ kyuudonut: 不算，Heap 要滿足 complete binary tree
※ 編輯: kyuudonut (140.116.1.136), 01/03/2017 14:57:50
→ ken52011219: Heap 為 complete binary tree 有可能再考出來QQ
推 Transfat: 對所以我的疑問是因為課本上都寫leftist tree又叫leftis
→ Transfat: t heap, 所以他沒有heap是個complete binary tree的性質
→ Transfat: 嗎？我原本想說complete B.T應該會是balanced的
→ ken52011219: 28 amortized 不是算worst cast 嗎 ?
→ ken52011219: 　　　　　　　　　　　　 case
推 Transfat: 阿阿我看到wiki了他說leftist tree is very unbalanced
→ ken52011219: leftist tree 不是complete binary tree
推 aa06697: leftist tree + min tree（或max)就叫做leftist heap唷
→ aa06697: 並不包含於heap 而以min tree看 他的合併是一直保留小的r
→ aa06697: oot的左子樹 右子樹再跟另一個樹合併 只要花O(logn)
→ aa06697: 期間要check有無符合leftist tree的性質 沒有要swap
大大可以幫我看一下 (c) 嗎
※ 編輯: kyuudonut (140.116.1.136), 01/03/2017 19:43:29
推 windwaker112: 因為c是在說leftest tree在insert的時候是將兩個tr
→ windwaker112: ee做合併 因為是合併原樹與一個one node tree
→ windwaker112: 刪除就是拿掉min  之後合併左子右子，這題的重點是
→ windwaker112: 在說要知道他還在繼續問左傾樹