[理工] 資結 winner/loser tree

[ok8752665 ()]

剛翻筆記的時候看到說

這兩個的時間複雜度一樣

但會選用loser 因參與比較點數較少 後只需和父點比較

可是我看了一下

winner後面也只需要跟sibling比

具體來說 loser是少了哪些比較阿

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.38.74.199 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1580284880.A.5D3.html
→ MASAGA: winner tree要全部重比
→ MASAGA: loser tree只有輸出的那條array需要往上重比(跟parent)
→ zuchang: delete min 的時候 winner要log k 但loser 只要O1
→ MASAGA: loser tree在delete min後不用花O(logn)維持嗎@@
→ bochengchen: winner tree 維持是O(n) loser tree是 O(logk) 吧
→ ok8752665: 複雜度不一樣嗎?
→ gcobc19622: 兩個時間一樣吧，只差在參與節點數loser比較少
→ gcobc19622: 比較次數應該是一樣，只是一個是跟parent比，一個是
→ gcobc19622: 跟sibling
→ ok8752665: 參與結點是什麼意思 為什麼比較次數一樣但參與結點較少