優(yōu)先隊列及其應(yīng)用ppt課件(參考版)
2025-05-09 00:31本頁面
【正文】 ? 二叉堆可以進(jìn)行的操作有：插入元素、刪除元素、取最值。 ? 隨著 i的增加，會有一些決策從第一類轉(zhuǎn)到第二類。 數(shù)據(jù)： 2 1 9 3 2 分析 (1) ? 設(shè) f(i)表示要將前 i個數(shù)改得合法需要的最少步數(shù)。 數(shù)據(jù)： 3 4 2 1 4 1 2 3 4 排序 ? 可是現(xiàn)在你做的輸入數(shù)據(jù)出了一些問題。 ? 例如右邊，就表示有兩組數(shù)據(jù)。輸入格式是這樣的： ? 試題有若干組數(shù)據(jù)。 ? 從外到內(nèi)初步處理，用小根堆存儲讀入的數(shù)據(jù)，每做一次初步累加結(jié)果即可。 共裝水： 2*4 + 3 + 1 = 12. 分析 ? “木桶效應(yīng)”：盛水的多少，不在于木桶上那塊最長的木板，而在于木桶上最短的那塊木板。 這些水晶塊都粘貼在一塊，之間不會漏水。顯然，使用大根堆即能滿足題目要求。 。每次將當(dāng)前的任務(wù) I加入 U后。 i。如果 CkCi+1那么根據(jù)定理 1，將 K,i+1替換后肯定更優(yōu)。如果第 i+1個任務(wù)直接加入后，依然滿足題目要求，那么前 i+1個任務(wù)最后方案集合就是 Ui+1=Ui+{i+1}。 分析 ? 考慮排序后前 i個任務(wù)組成的最優(yōu)方案集合是Ｕ i。如果存在一個不屬于 U的任務(wù) j，對于某個屬于Ｕ的Ｉ滿足 TjTi而且Ｃ jCi。這時候我們可以采用貪心方法，盡量選截止時間比較晚，同時需要時間比較少的任務(wù)完成是最好的?，F(xiàn)在你一個人希望從 0時刻開始完成盡量多的任務(wù)。 二項隊列（ binomial queue） ? 二項樹（ binomial tree，堆序樹）的森林 ? 二項樹的結(jié)構(gòu) ——遞歸構(gòu)造 –高度為 0， B0：單節(jié)點(diǎn)樹 –高度為 k， Bk：由一棵二項樹 Bk1附接到另一棵Bk1的根上而得 二項樹例 二項樹特性 ? Bk的根節(jié)點(diǎn)的子樹為 B0、 B ...、 Bk1 ? 高度為 k的二項樹恰有 2k個節(jié)點(diǎn) ? d層的節(jié)點(diǎn)數(shù)目為二項系數(shù) ? 令二項樹為堆序，且每個高度僅有一棵二項樹，則可用二項隊列惟一表示任意大小的優(yōu)先隊列 ??????dk二項隊列表示優(yōu)先隊列例 ? 優(yōu)先隊列大小為 13： 1101，顯然每個 1對應(yīng)一棵二項樹， B B B0 ? 6個元素的優(yōu)先隊列表示為下圖二項隊列 取最小元操作 ? 取所有二項樹根節(jié)點(diǎn)中最小者 ? O(logN) ? 在其他操作過程中記錄最小根節(jié)點(diǎn)，則可提高到 O(1) 合并操作 ? 二進(jìn)制數(shù)相加 – 6個元素和 12個元素的二項隊列合并 – 110+1100——由低至高逐位相加 ? 0+0=0：兩個隊列均無 B0，合并后自然也沒有 ? 1+0=1：一個隊列有 B1，另一個沒有，合并后隊列中的 B1自然來自前者 ? 1+1=10：將兩個 B2中根較大者附接到較小者，得到一個 B3（進(jìn)位），結(jié)果中無 B2 ? 0+1+1=10：類似步驟三，得到一個 B4，結(jié)果中無 B3 ? 10010：結(jié)果二項隊列包含一個 B1和一個 B4 合并操作例 13放入結(jié)果隊列 兩個 B1合并為 B2 最終結(jié)果 ? 三個 B2，兩個合并變?yōu)?B3，一個保留 O(logN) 插入操作 ? 最壞情況 O(logN) ? 精確：最低位起，第一個 0在第 i位，則運(yùn)行時間正比于 i+1 ? 每位為 0的概率為 1/2?平均情況 O(1) 例：將 1至 7插入空二項隊列 DeleteMin ? 先找到具有最小根的二項樹 Bk， O(logN) ? 將 Bk從二項隊列中去掉，得到新的二項隊列 H’ ? 將 Bk的根去掉，其子樹構(gòu)成二項隊列 H’’ ? 將 H’和 H’’合并即可， O(logN) DeleteMin例 ? 顯然應(yīng)該刪除 B3的根 12 DeleteMin例（續(xù)） ? H’和 H’’為 DeleteMin例（續(xù)） ? H’和 H’’合并后結(jié)果為 二項隊列的實(shí)現(xiàn) 二叉樹表示樹 較大的子樹更靠前（左） 攤還分析 ? amortization analysis – 一般的復(fù)雜性分析 ——算法運(yùn)行一次所需要的時間 – 算法如果運(yùn)行不只一次呢？ ? 如果每次運(yùn)行之間相互無關(guān) ——同樣 OK ? 但如果多次運(yùn)行之間是相關(guān)的呢？ – 考慮多次運(yùn)行的總時間，再除以運(yùn)行次數(shù)，得到一個“平均時間” ——注意區(qū)分平均情況時間復(fù)雜性 – 很多算法，單獨(dú)考慮一次運(yùn)行，最壞情況很差，但攤還分析表明其連續(xù)運(yùn)行性能很好 二項隊列的創(chuàng)建 ? 對空二項隊列中進(jìn)行 N次插入操作 ? 每次操作：一個二進(jìn)制數(shù) ***…*** + 1 ? 倒數(shù)第一個 0在倒數(shù)第 c位 ?花費(fèi)時間 c ? 二進(jìn)制數(shù)的變化： 0, 1, …, N 1, N –第 0, 2, 4, 6… 次操作，花費(fèi) 1 –第 1, 5, … 次操作，花費(fèi) 2 –… –時間復(fù)雜性 O(N) 創(chuàng)建操作的攤還分析 ? 倒數(shù)第一個 0在倒數(shù)第 c位 ?花費(fèi)時間 c，效果是去掉了 c1棵樹，增加一棵樹，二項樹的數(shù)目變化為 2c ? 令 Ci為第 i次插入代價， Ti為第 i次插入后樹的數(shù)目，則 T0=0，可得到公式 Ci+(Ti – Ti1)=2 ? 因此 C1+(T1 – T0)=2 C2+(T2 –
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1