多路归并排序的时候，为什么要采用败者树?
推荐
在线提问>>
一、多路归并排序的时候采用败者树
因为在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。 所以总的来说，减少了访存的时间。（拿空间换时间）胜者树以小为胜的话，如果比较兄弟节点发现更小直接替代父节点即可。如果更大则兄弟节点胜出。。
其实一开始就是用堆来完成多路归并的，但是人们发现堆每次取出最小值之后，把最后一个数放到堆顶，调整堆的时候，每次都要选出父节点的左右两个孩子节点的最小值，然后再用孩子节点的最小值和父节点进行比较，所以每调整一层需要比较两次。 这时人们想能否简化比较过程，这时就有了胜者树。
这样每次比较只用跟自己的兄弟节点进行比较就好，所以用胜者树可以比堆少一半的比较次数。 而胜者树在节点上升的时候首先需要获得父节点，然后再获得兄弟节点，然后再比较。这时人们又想能否再次减少比较次数，于是就有了败者树。所以总的来说，减少了访存的时间。
延伸阅读：
二、堆，赢者树，败者树的相同点和不同点
相同点
首先它们三个的相同点就是在于：空间和时间复杂度都是一样的。调整一次的时间复杂度都是O(logN)的。 所以这道题用堆来做，跟用败者树来做并没有本质上的算法复杂度量级上的差别。
不同点
其实一开始就是只有堆来完成多路归并的，但是人们发现堆每次取出最小值之后，把最后一个数放到堆顶，调整堆的时候，每次都要选出父节点的两个孩子节点的最小值，然后再用孩子节点的最小值和父节点进行比较，所以每调整一层需要比较两次。 这时人们想能否简化比较过程，这时就有了胜者树 。
这样每次比较只用跟自己的兄弟节点进行比较就好，所以用胜者树可以比堆少一半的比较次数。 而胜者树在节点上升的时候优选需要获得父节点，然后再获得兄弟节点，然后再比较。这时人们又想能否再次减少比较次数，于是就有了败者树。在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。 所以总的来说，减少了访存的时间。
