多路歸併排序的時候，為什麼要採用敗者樹？

02-01

在進行多路歸併時，如果採用勝者樹，在更新葉子結點時，會維護從該葉子結點到根的這條路徑上的winner，進行比較的是兄弟結點，而敗者樹，是與其父親進行比較，更新loser，兩者的比較次數是一樣的。
如果採用堆的話，其與敗者樹的效率分析如下：

敗者樹在維護的時候，比較次數是logn+1, 敗者樹從下往上維護，每上一層，只需要和父節點比較一次，而堆是自上往下維護，每一層需要和左右子節點都比較，需要比較兩次，從這個角度，敗者樹比堆更優一點，但是，敗者樹每一次維護，必然是從葉子節點到根節點的一條路徑，而堆維護的時候有可能在中間某個層次停止，這樣敗者樹雖然每層比堆比較的次數少，但是堆比較的層數可能比較少。

既然如此，那麼為什麼在進行多路歸併排序時，往往採用的是敗者樹，而不是與其效率相當的勝者樹或者heap呢？

比較每次操作的代價，同時試圖理解緩存工作原理

在用勝者樹的時候，每個新元素上升時，首先需要獲得父節點，然後再獲得兄弟節點，然後再比較。

在使用敗者樹的時候，每個新元素上升時，只需要獲得父節點並比較即可。

所以總的來說，減少了訪存的時間。

其實現在程序的主要瓶頸在於訪存了，計算倒幾乎可以忽略不計了。

之前我剛好總結過這個：堆，贏者樹，敗者樹的區別與聯繫 - haolexiao的專欄 - 博客頻道 - CSDN.NET

堆，贏者樹，敗者樹的相同點和不同點總結如下

相同點

首先它們三個的相同點就是在於：空間和時間複雜度都是一樣的。調整一次的時間複雜度都是O(logN)的。
所以這道題用堆來做，跟用敗者樹來做並沒有本質上的演算法複雜度量級上的差別。

不同點

其實一開始就是只有堆來完成多路歸併的，但是人們發現堆每次取出最小值之後，把最後一個數放到堆頂，調整堆的時候，每次都要選出父節點的兩個孩子節點的最小值，然後再用孩子節點的最小值和父節點進行比較，所以每調整一層需要比較兩次。
這時人們想能否簡化比較過程，這時就有了勝者樹

這樣每次比較只用跟自己的兄弟節點進行比較就好，所以用勝者樹可以比堆少一半的比較次數。
而勝者樹在節點上升的時候首選需要獲得父節點，然後再獲得兄弟節點，然後再比較。這時人們又想能否再次減少比較次數，於是就有了敗者樹

在使用敗者樹的時候，每個新元素上升時，只需要獲得父節點並比較即可。
所以總的來說，減少了訪存的時間。
最後就是 @黃尼瑪說的現在程序的主要瓶頸在於訪存了，計算倒幾乎可以忽略不計了。

敗者樹與勝者樹：

勝者樹和敗者樹在每輸出和補充一個值之後都要自底向上調整，每上升一層都需要一次比較，敗者樹是和父節點的一次比較，勝者樹是和兄弟的一次比較，在比較的內存訪問次數上二者沒有太大的差別(或者勝者樹可能好一點)。不同的是勝者樹每次必然需要更新勝者(因為這條路徑就是以原來的最終勝者為外部節點的路徑，而原來的最終勝者已經被輸出了)，但敗者樹每次不一定需要更新，這就代表它在每次上升時可能會少一次向內存的寫入，因此更優。

@黃尼瑪的答案中「勝者樹每上升一次需要訪問兩個節點：父節點和兄弟節點；而敗者樹只需要訪問父節點。這就是訪存優勢。」比較好的回答了這個問題。

做一點設計層面的補充：

由於新加入的節點一定是替換了上一輪的勝者，那麼對於勝者堆，從新節點到根之間路徑節點存的都是上一輪的勝者，這些數據事實上對於本輪比較來說是無用的，但每次還要與兄弟節點比較去更新它。

而敗者堆中，對於新更新的節點，它的父節點都是兄弟子堆的勝者，是最有價值、值得比較的數據，每次更新也都可以直接用於下輪比較。