本文主要是介绍堆，赢者树，败者树的区别与联系，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天做LeetCode的23. Merge k Sorted Lists这道题的时候，遇到的这个问题。这道题本质上就是一个多路归并的问题，而这道题主要就是考察多路归并时候的选择问题。按照之前本科上课学的，最好的办法就是用竞赛树(败者树)，可是我嫌麻烦就用堆来做了，也顺利能过。所以就想到，堆，赢者树，败者树到底有什么区别呢？
于是找了一些资料看了一下，在这里总结一下
相同点
首先它们三个的相同点就是在于：空间和时间复杂度都是一样的。调整一次的时间复杂度都是O(logN)的。
所以这道题用堆来做，跟用败者树来做并没有本质上的算法复杂度量级上的差别。
不同点
其实一开始就是只有堆来完成多路归并的，但是人们发现堆每次取出最小值之后，把最后一个数放到堆顶，调整堆的时候，每次都要选出父节点的两个孩子节点的最小值，然后再用孩子节点的最小值和父节点进行比较，所以每调整一层需要比较两次。
这时人们想能否简化比较过程，这时就有了胜者树
圆圈内是胜利者的下标，方块内是数组内的值，b0,b1..b4表示的是下标, ls表示圆圈的下标
这样每次比较只用跟自己的兄弟节点进行比较就好，所以用胜者树可以比堆少一半的比较次数。
而胜者树在节点上升的时候首选需要获得父节点，然后再获得兄弟节点，然后再比较。这时人们又想能否再次减少比较次数，于是就有了败者树
在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。
所以总的来说，减少了访存的时间。
现在程序的主要瓶颈在于访存了，计算倒几乎可以忽略不计了。
————————————————
版权声明：本文为CSDN博主「哈乐笑」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/haolexiao/article/details/53488314
这篇关于堆，赢者树，败者树的区别与联系的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
