一、多路歸并排序的時(shí)候采用敗者樹(shù)

因?yàn)樵谑褂脭≌邩?shù)的時(shí)候，每個(gè)新元素上升時(shí)，只需要獲得父節(jié)點(diǎn)并比較即可。 所以總的來(lái)說(shuō)，減少了訪存的時(shí)間。（拿空間換時(shí)間）勝者樹(shù)以小為勝的話，如果比較兄弟節(jié)點(diǎn)發(fā)現(xiàn)更小直接替代父節(jié)點(diǎn)即可。如果更大則兄弟節(jié)點(diǎn)勝出。。

其實(shí)一開(kāi)始就是用堆來(lái)完成多路歸并的，但是人們發(fā)現(xiàn)堆每次取出最小值之后，把最后一個(gè)數(shù)放到堆頂，調(diào)整堆的時(shí)候，每次都要選出父節(jié)點(diǎn)的左右兩個(gè)孩子節(jié)點(diǎn)的最小值，然后再用孩子節(jié)點(diǎn)的最小值和父節(jié)點(diǎn)進(jìn)行比較，所以每調(diào)整一層需要比較兩次。 這時(shí)人們想能否簡(jiǎn)化比較過(guò)程，這時(shí)就有了勝者樹(shù)。

這樣每次比較只用跟自己的兄弟節(jié)點(diǎn)進(jìn)行比較就好，所以用勝者樹(shù)可以比堆少一半的比較次數(shù)。 而勝者樹(shù)在節(jié)點(diǎn)上升的時(shí)候首先需要獲得父節(jié)點(diǎn)，然后再獲得兄弟節(jié)點(diǎn)，然后再比較。這時(shí)人們又想能否再次減少比較次數(shù)，于是就有了敗者樹(shù)。所以總的來(lái)說(shuō)，減少了訪存的時(shí)間。

延伸閱讀：

二、堆，贏者樹(shù)，敗者樹(shù)的相同點(diǎn)和不同點(diǎn)

相同點(diǎn)

首先它們?nèi)齻€(gè)的相同點(diǎn)就是在于：空間和時(shí)間復(fù)雜度都是一樣的。調(diào)整一次的時(shí)間復(fù)雜度都是O(logN)的。 所以這道題用堆來(lái)做，跟用敗者樹(shù)來(lái)做并沒(méi)有本質(zhì)上的算法復(fù)雜度量級(jí)上的差別。

不同點(diǎn)

其實(shí)一開(kāi)始就是只有堆來(lái)完成多路歸并的，但是人們發(fā)現(xiàn)堆每次取出最小值之后，把最后一個(gè)數(shù)放到堆頂，調(diào)整堆的時(shí)候，每次都要選出父節(jié)點(diǎn)的兩個(gè)孩子節(jié)點(diǎn)的最小值，然后再用孩子節(jié)點(diǎn)的最小值和父節(jié)點(diǎn)進(jìn)行比較，所以每調(diào)整一層需要比較兩次。 這時(shí)人們想能否簡(jiǎn)化比較過(guò)程，這時(shí)就有了勝者樹(shù) 。

這樣每次比較只用跟自己的兄弟節(jié)點(diǎn)進(jìn)行比較就好，所以用勝者樹(shù)可以比堆少一半的比較次數(shù)。 而勝者樹(shù)在節(jié)點(diǎn)上升的時(shí)候優(yōu)選需要獲得父節(jié)點(diǎn)，然后再獲得兄弟節(jié)點(diǎn)，然后再比較。這時(shí)人們又想能否再次減少比較次數(shù)，于是就有了敗者樹(shù)。在使用敗者樹(shù)的時(shí)候，每個(gè)新元素上升時(shí)，只需要獲得父節(jié)點(diǎn)并比較即可。 所以總的來(lái)說(shuō)，減少了訪存的時(shí)間。