勝者樹與敗者樹
勝者樹和敗者樹都是完全二叉樹，是樹形選擇排序的一種變型。每個葉子結點相當于一個選手，每個中間結點相當于一場比賽，每一層相當于一輪比賽。
不同的是，勝者樹的中間結點記錄的是勝者的标号；而敗者樹的中間結點記錄的敗者的标号。
勝者樹與敗者樹可以在log(n)的時間内找到最值。任何一個葉子結點的值改變後，利用中間結點的資訊，還是能夠快速地找到最值。在k路歸并排序中經常用到。
一、勝者樹
勝者樹的一個優點是，如果一個選手的值改變了，可以很容易地修改這棵勝者樹。隻需要沿着從該結點到根結點的路徑修改這棵二叉樹，而不必改變其他比賽的結果。
fig. 1
fig.1是一個勝者樹的示例。規定數值小者勝。
1. b3 pk b4，b3勝b4負，内部結點ls[4]的值為3；
2. b3 pk b0，b3勝b0負，内部結點ls[2]的值為3；
3. b1 pk b2，b1勝b2負，内部結點ls[3]的值為1；
4. b3 pk b1，b3勝b1負，内部結點ls[1]的值為3。.
當fig. 1中葉子結點b3的值變為11時，重構的勝者樹如fig. 2所示。
2. b3 pk b0，b0勝b3負，内部結點ls[2]的值為0；
4. b0 pk b1，b1勝b0負，内部結點ls[1]的值為1。.
fig. 2
二、敗者樹
敗者樹是勝者樹的一種變體。在敗者樹中，用父結點記錄其左右子結點進行比賽的敗者，而讓勝者參加下一輪的比賽。敗者樹的根結點記錄的是敗者，需要加一個結點來記錄整個比賽的勝利者。采用敗者樹可以簡化重構的過程。
fig. 3
fig. 3是一棵敗者樹。規定數大者敗。
1. b3 pk b4，b3勝b4負，内部結點ls[4]的值為4；
2. b3 pk b0，b3勝b0負，内部結點ls[2]的值為0；
3. b1 pk b2，b1勝b2負，内部結點ls[3]的值為2；
4. b3 pk b1，b3勝b1負，内部結點ls[1]的值為1；
5. 在根結點ls[1]上又加了一個結點ls[0]=3，記錄的最後的勝者。
敗者樹重構過程如下：
· 将新進入選擇樹的結點與其父結點進行比賽：将敗者存放在父結點中；而勝者再與上一級的父結點比較。
· 比賽沿着到根結點的路徑不斷進行，直到ls[1]處。把敗者存放在結點ls[1]中，勝者存放在ls[0]中。
fig. 4
fig. 4是當b3變為13時，敗者樹的重構圖。
注意，敗者樹的重構跟勝者樹是不一樣的，敗者樹的重構隻需要與其父結點比較。對照fig.
3來看，b3與結點ls[4]的原值比較，ls[4]中存放的原值是結點4，即b3與b4比較，b3負b4勝，則修改ls[4]的值為結點3。同理，以此
類推，沿着根結點不斷比賽，直至結束。
由上可知，敗者樹簡化了重構。敗者樹的重構隻是與該結點的父結點的記錄有關，而勝者樹的重構還與該結點的兄弟結點有關。
一 外部排序的基本思路
假設有一個72kb的檔案，其中存儲了18k個整數，磁盤中實體塊的大小為4kb，将檔案分成18組，每組剛好4kb。
首先通過18次内部排序，把18組資料排好序，得到初始的18個歸并段r1~r18，每個歸并段有1024個整數。
然後對這18個歸并段使用4路平衡歸并排序：
第1次歸并：産生5個歸并段
r11 r12 r13 r14 r15
其中
r11是由{r1,r2,r3,r4}中的資料合并而來
r12是由{r5,r6,r7,r8}中的資料合并而來
r13是由{r9,r10,r11,r12}中的資料合并而來
r14是由{r13,r14,r15,r16}中的資料合并而來
r15是由{r17,r18}中的資料合并而來
把這5個歸并段的資料寫入5個檔案：
foo_1.dat foo_2.dat foo_3.dat foo_4.dat foo_5.dat
第2次歸并：從第1次歸并産生的5個檔案中讀取資料，合并，産生2個歸并段
r21 r22
其中r21是由{r11,r12,r13,r14}中的資料合并而來
其中r22是由{r15}中的資料合并而來
把這2個歸并段寫入2個檔案
bar_1.dat bar_2.dat
第3次歸并：從第2次歸并産生的2個檔案中讀取資料，合并，産生1個歸并段
r31
r31是由{r21,r22}中的資料合并而來
把這個檔案寫入1個檔案
foo_1.dat
此即為最終排序好的檔案。
參考文章：
<a href="http://blog.csdn.net/whz_zb/article/details/7425152" target="_blank">http://blog.csdn.net/whz_zb/article/details/7425152</a>