第十章外部排序-展示頁(yè)
2024-10-23 11:40本頁(yè)面
【正文】 5 2 0 1 3 6 90 0 10 9 20 6 8 12 1 2 3 4 5 6 調(diào)整敗者樹的方法 : 將新補(bǔ)充的結(jié)點(diǎn)與其雙親結(jié)點(diǎn)比較 , 敗者留在該雙親結(jié)點(diǎn) ,勝者繼續(xù)向上直至樹根的雙親 以在 b[4]補(bǔ)充 15為例 15 4與 3比較 4與 2比較 4 2與 5比較 2 5 調(diào)整敗者樹的方法 7 7 7 7 7 7 7 90 0 10 9 20 6 8 12 1 2 3 4 5 6 [k路歸并對(duì)內(nèi)存的要求 ] 至少要有 k個(gè)輸入緩沖區(qū)和一個(gè)輸出緩沖區(qū) 建敗者樹的過(guò)程 7 1 初始化敗者樹調(diào)整 b[6] 6 調(diào)整 b[5] 5 調(diào)整 44 調(diào)整 334 調(diào)整 22 調(diào)整 11 2 4 調(diào)整 005 4 建敗者樹的過(guò)程 [數(shù)據(jù)結(jié)構(gòu) ] (依據(jù)：敗者樹為完全二叉樹 ) ? 主： b[0.. k] b[0.. k1]—— k個(gè)葉結(jié)點(diǎn) ，存放 k個(gè)輸入歸并段中當(dāng)前 參加歸并的記錄（緩沖區(qū)） b[k]—— 虛擬記錄，該關(guān)鍵字取可能的最小值 minkey ? 輔： ls[0.. k1] —— 不含葉結(jié)點(diǎn)的敗者樹 存放最后勝出的編號(hào)（ ls[0]）以及所記錄的敗者編號(hào) [處理步驟 ] ? 建敗者樹 ls[0.. k1] ? 重復(fù)下列操作直至 k路歸并完畢 ? 將 b[ls[0]]寫至輸出歸并段 ? 補(bǔ)充記錄 (某歸并段變空時(shí) ,補(bǔ) ?)，調(diào)整敗者樹 多路平衡歸并算法 算法描述：建立敗者樹 void CreateLoserTree() { b[k] = MINKEY。第十章 外部排序 本章內(nèi)容 ?外存信息的存取 ?外部排序的基本方法 — 歸并排序法 ?多路平衡歸并 ?置換 選擇排序 外部排序的應(yīng)用對(duì)象 保存在外存儲(chǔ)器上的信息量很大的數(shù)據(jù)記錄文件。 外排序與內(nèi)排序的差別
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1