一、多路歸并排序的時候采用敗者樹
因為在使用敗者樹的時候,每個新元素上升時,只需要獲得父節(jié)點并比較即可。 所以總的來說,減少了訪存的時間。(拿空間換時間)勝者樹以小為勝的話,如果比較兄弟節(jié)點發(fā)現(xiàn)更小直接替代父節(jié)點即可。如果更大則兄弟節(jié)點勝出。。
其實一開始就是用堆來完成多路歸并的,但是人們發(fā)現(xiàn)堆每次取出最小值之后,把最后一個數(shù)放到堆頂,調(diào)整堆的時候,每次都要選出父節(jié)點的左右兩個孩子節(jié)點的最小值,然后再用孩子節(jié)點的最小值和父節(jié)點進(jìn)行比較,所以每調(diào)整一層需要比較兩次。 這時人們想能否簡化比較過程,這時就有了勝者樹。
這樣每次比較只用跟自己的兄弟節(jié)點進(jìn)行比較就好,所以用勝者樹可以比堆少一半的比較次數(shù)。 而勝者樹在節(jié)點上升的時候首先需要獲得父節(jié)點,然后再獲得兄弟節(jié)點,然后再比較。這時人們又想能否再次減少比較次數(shù),于是就有了敗者樹。所以總的來說,減少了訪存的時間。
延伸閱讀:
二、堆,贏者樹,敗者樹的相同點和不同點
相同點
首先它們?nèi)齻€的相同點就是在于:空間和時間復(fù)雜度都是一樣的。調(diào)整一次的時間復(fù)雜度都是O(logN)的。 所以這道題用堆來做,跟用敗者樹來做并沒有本質(zhì)上的算法復(fù)雜度量級上的差別。
不同點
其實一開始就是只有堆來完成多路歸并的,但是人們發(fā)現(xiàn)堆每次取出最小值之后,把最后一個數(shù)放到堆頂,調(diào)整堆的時候,每次都要選出父節(jié)點的兩個孩子節(jié)點的最小值,然后再用孩子節(jié)點的最小值和父節(jié)點進(jìn)行比較,所以每調(diào)整一層需要比較兩次。 這時人們想能否簡化比較過程,這時就有了勝者樹 。
這樣每次比較只用跟自己的兄弟節(jié)點進(jìn)行比較就好,所以用勝者樹可以比堆少一半的比較次數(shù)。 而勝者樹在節(jié)點上升的時候優(yōu)選需要獲得父節(jié)點,然后再獲得兄弟節(jié)點,然后再比較。這時人們又想能否再次減少比較次數(shù),于是就有了敗者樹。在使用敗者樹的時候,每個新元素上升時,只需要獲得父節(jié)點并比較即可。 所以總的來說,減少了訪存的時間。