多路归并排序为啥要用败者树？

2020-05-03 本文已影响0人小幸运Q

堆排序的时间复杂度跟败者树的时间复杂度一致，都是 $O(n*k*log_k(n) + k) =O(nklog_kn)$ 为什么不用堆？

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

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

在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。所以总的来说，减少了访存的时间。（拿空间换时间）

原因：胜者树以小为胜的话，如果比较兄弟节点发现更小直接替代父节点即可，如果更大则兄弟节点胜出。
败者树比较父节点指向的点发现更大直接替换败者即可，更小则不需要替换然后接着上移。

二者都是顶点缺失，都要从底部叶节点遍历到顶点。

最后就是现在程序的主要瓶颈在于访存了，计算倒几乎可以忽略不计。