多路归并排序的时候，为什么要采用败者树?

来源：千锋教育

发布人：xqq

时间：2023-10-20 22:24:11

一、多路归并排序的时候采用败者树

因为在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。所以总的来说，减少了访存的时间。（拿空间换时间）胜者树以小为胜的话，如果比较兄弟节点发现更小直接替代父节点即可。如果更大则兄弟节点胜出。。

其实一开始就是用堆来完成多路归并的，但是人们发现堆每次取出最小值之后，把最后一个数放到堆顶，调整堆的时候，每次都要选出父节点的左右两个孩子节点的最小值，然后再用孩子节点的最小值和父节点进行比较，所以每调整一层需要比较两次。这时人们想能否简化比较过程，这时就有了胜者树。

这样每次比较只用跟自己的兄弟节点进行比较就好，所以用胜者树可以比堆少一半的比较次数。而胜者树在节点上升的时候首先需要获得父节点，然后再获得兄弟节点，然后再比较。这时人们又想能否再次减少比较次数，于是就有了败者树。所以总的来说，减少了访存的时间。

延伸阅读：

二、堆，赢者树，败者树的相同点和不同点

相同点

首先它们三个的相同点就是在于：空间和时间复杂度都是一样的。调整一次的时间复杂度都是O(logN)的。所以这道题用堆来做，跟用败者树来做并没有本质上的算法复杂度量级上的差别。

不同点

其实一开始就是只有堆来完成多路归并的，但是人们发现堆每次取出最小值之后，把最后一个数放到堆顶，调整堆的时候，每次都要选出父节点的两个孩子节点的最小值，然后再用孩子节点的最小值和父节点进行比较，所以每调整一层需要比较两次。这时人们想能否简化比较过程，这时就有了胜者树。

这样每次比较只用跟自己的兄弟节点进行比较就好，所以用胜者树可以比堆少一半的比较次数。而胜者树在节点上升的时候优选需要获得父节点，然后再获得兄弟节点，然后再比较。这时人们又想能否再次减少比较次数，于是就有了败者树。在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。所以总的来说，减少了访存的时间。

声明：本站稿件版权均属千锋教育所有，未经许可不得擅自转载。