一、多路歸并排序的時候采用敗者樹

因為在使用敗者樹的時候，每個新元素上升時，只需要獲得父節點并比較即可。 所以總的來說，減少了訪存的時間。（拿空間換時間）勝者樹以小為勝的話，如果比較兄弟節點發現更小直接替代父節點即可。如果更大則兄弟節點勝出。。

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

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

延伸閱讀：

二、堆，贏者樹，敗者樹的相同點和不同點

相同點

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

不同點

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

這樣每次比較只用跟自己的兄弟節點進行比較就好，所以用勝者樹可以比堆少一半的比較次數。 而勝者樹在節點上升的時候優選需要獲得父節點，然后再獲得兄弟節點，然后再比較。這時人們又想能否再次減少比較次數，于是就有了敗者樹。在使用敗者樹的時候，每個新元素上升時，只需要獲得父節點并比較即可。 所以總的來說，減少了訪存的時間。