1樓：田冬冬
首先勝者樹敗者樹都叫Tournament Tree，所謂多路歸併場景是指不斷poll、offer各多路資料的過程。
那麼維護操作（不是建立）比較如下：
堆是頂點資料彈出後，最後的葉子節點代替其位置，然後做比較倆子節點下沉動作，新來的資料再放在最新的葉子節點，再做比較父節點上浮動作。維護成本O(2H+H),H是樹高度
勝者樹是頂點資料彈出後，其頂點到葉子節點全路更新，更新順序是自下而上，靠子節點比較結果更新父節點。維護成本O(H)
敗者樹是新資料進入葉子節點後，也是自下而上更新，但只和父節點比較，而且更新概率是1/2 維護成本O(H/2)
堆https://
visualgo.net/en/heap
敗者樹https://www.
勝者樹https://www.
geeksforgeeks.org/tourn
ament-tree-and-binary-heap/
2樓：張昭
之前我剛好總結過這個：堆，贏者樹，敗者樹的區別與聯絡 - haolexiao的專欄 - 部落格頻道 - CSDN.NET
堆，贏者樹，敗者樹的相同點和不同點總結如下
相同點
首先它們三個的相同點就是在於：空間和時間複雜度都是一樣的。調整一次的時間複雜度都是O(logN)的。
所以這道題用堆來做，跟用敗者樹來做並沒有本質上的演算法複雜度量級上的差別。
不同點
其實一開始就是只有堆來完成多路歸併的，但是人們發現堆每次取出最小值之後，把最後乙個數放到堆頂，調整堆的時候，每次都要選出父節點的兩個孩子節點的最小值，然後再用孩子節點的最小值和父節點進行比較，所以每調整一層需要比較兩次。
這時人們想能否簡化比較過程，這時就有了勝者樹
這樣每次比較只用跟自己的兄弟節點進行比較就好，所以用勝者樹可以比堆少一半的比較次數。
而勝者樹在節點上公升的時候首選需要獲得父節點，然後再獲得兄弟節點，然後再比較。這時人們又想能否再次減少比較次數，於是就有了敗者樹
在使用敗者樹的時候，每個新元素上公升時，只需要獲得父節點並比較即可。
所以總的來說，減少了訪存的時間。
最後就是 @黃尼瑪說的現在程式的主要瓶頸在於訪存了，計算倒幾乎可以忽略不計了。
3樓：QKMICS
敗者樹與勝者樹：
勝者樹和敗者樹在每輸出和補充乙個值之後都要自底向上調整，每上公升一層都需要一次比較，敗者樹是和父節點的一次比較，勝者樹是和兄弟的一次比較，在比較的記憶體訪問次數上二者沒有太大的差別(或者勝者樹可能好一點)。不同的是勝者樹每次必然需要更新勝者(因為這條路徑就是以原來的最終勝者為外部節點的路徑，而原來的最終勝者已經被輸出了)，但敗者樹每次不一定需要更新，這就代表它在每次上公升時可能會少一次向記憶體的寫入，因此更優。
4樓：spiritsaway
在用勝者樹的時候，每個新元素上公升時，首先需要獲得父節點，然後再獲得兄弟節點，然後再比較。
在使用敗者樹的時候，每個新元素上公升時，只需要獲得父節點並比較即可。
所以總的來說，減少了訪存的時間。
其實現在程式的主要瓶頸在於訪存了，計算倒幾乎可以忽略不計了。
為什麼訊號重建的時候，一般採用sinc作為插值訊號？
葉某人 我從空間的角度說下 首先證明sinc函式是空間的一組orthogonal basis 設,其中為取樣時間 int sinc t n sinc m t dt int sinc boldsymbol sinc m n boldsymbol d boldsymbol sinc sinc m n e...
安卓 QQ 為什麼要採用 iOS 7 的扁平風格？
如同Metro，Android Design 同樣不是 看上去很簡單 大多數產品經理 UE UI對於iOS風格已經熟悉，並且可參照的範例更多。同時他們對Android Design並沒有過多的研究過，甚至我遇到的大多數這些人使用的基本是iOS裝置，使用Android也大多使用三星裝置。所以對於And...
Java HashMap擴容的時候，為什麼要把Entry鍊錶反轉？這樣做有什麼好處嗎？
Absurd 這是 jdk1.7的原始碼 void resize int newCapacity Entry newTable new Entry newCapacity transfer newTable initHashSeedAsNeeded newCapacity table newTabl...