[理工] 資演 選擇樹

[newpuma (還很新)]

http://i.imgur.com/8RMdNtx.jpg

(1)想請教這題選擇樹中，沒有說是要選擇最大還是最小一般來說是選最大嗎？

這樣畫出來是選最大的出來然後開始競賽對嗎

(2)
一個元素被output是哪一個元素被output呢，root嗎？output之後的樹是從run裡頭重新挑次大的再重新比較嗎？

(3)
想問一個觀念，loser tree一開始的leaf是不是也一樣？(假設是max，那麽run裡頭挑出最大的元素，慢慢比較上去，輸的當root沒錯吧？)

(4)
我覺得是nlogn 不知道有沒有想錯？

每一次元素更動，比較次數不超過樹高，因為是complete tree所以log n，最多n次

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.200.66
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485138022.A.941.html
推 yupog2003: 這題應該是成大103程式設計
→ yupog2003: (1)我看這題的每個run都是由小到大，所以我認為winner
→ yupog2003: 應該是比較小的數才對
→ yupog2003: (2)應該是root沒錯
output節點後，run裡頭直接刪去一個element就好嗎？
→ yupog2003: (3)可以參考這裡：https://goo.gl/UpjHZ6
→ yupog2003: (4)應為nlogk，因為只有k個run，樹高為logk
推 AllenPaul: 我也覺得應該是小的winner 看下方排列得知
→ AllenPaul: 不然推出來的winner不會是最大數 相反得知 要推出最小
原來如此 謝謝！
※ 編輯: newpuma (223.137.200.66), 01/23/2017 13:52:29