優(yōu)先隊(duì)列及其應(yīng)用ppt課件(編輯修改稿)
2025-06-02 00:31 本頁面
【文章內(nèi)容簡(jiǎn)介】 操作 –元素 x插入到名為 H的最大 HBLT ? ? 構(gòu)造只有一個(gè)元素 x的最大 HBLT H’ ? ?H’與 H合并 ? 刪除操作也可借助合并操作 –刪除根節(jié)點(diǎn) ? ? 兩個(gè)子樹 L、 R均為最大 HBLT ? 合并 L、 R 最大 HBLT的合并操作 ? 遍歷 右路徑 ——O(logn) ? 遞歸，合并 A、 B –若一個(gè)為空，則另一個(gè)為合并結(jié)果 –若都不空 ? 比較兩個(gè)根節(jié)點(diǎn)，較大者為新的根 ? 假定 A較大，左子樹為 L，右子樹為 R ? 遞歸方法將 R與 B合并為 C ? 最終合并結(jié)果： A的根為根； L、 C的 s值較大者為左子樹，另一個(gè)為右子樹 插入操作實(shí)例 1 A B 插入操作實(shí)例 2 A B 插入操作實(shí)例 3 A B 插入操作實(shí)例 4 A B 初始化最大 HBLT ? n個(gè)元素依次插入空 HBLT： O(nlogn) ? 線性時(shí)間算法 –構(gòu)造 n個(gè)單元素的 HBLT?FIFO隊(duì)列 –刪除隊(duì)列前兩個(gè) HBLT?合并，加入隊(duì)尾 –重復(fù)，直至只剩一個(gè) HBLT 初始化實(shí)例 希望構(gòu)造具有五個(gè)元素： 7 , 1 , 9 , 11 , 2 的一棵最大 H B LT。如下圖： ① 7,1合并成為 a) ② 9,11合并成為 b) ③ 2和 a)合并成為 c) ④ 最后 b)和 c)合并成為 d) 復(fù)雜性分析 ? 初始化的復(fù)雜性 – n是 2的冪：合并 n/2對(duì)一個(gè)元素的 HBLT?合并n/4對(duì)二個(gè)元素的 HBLT... –合并兩棵 2i個(gè)元素的 HBLT： O(i+1) –總時(shí)間復(fù)雜性 )()2()8*34*22( nOinOnnnO i ????? ??斜堆（ skew heap） ? 斜堆可遞歸的定義如下： ● 只有一個(gè)元素的堆是斜堆。 ● 兩個(gè)斜堆通過斜堆的合并操作，得到的結(jié)果仍是斜堆 ? 與左高樹類似，但無“左高”這一限制 ? 各種操作與左高樹類似，也是以合并為基礎(chǔ) ? 但遞歸合并過程中，左右孩子的交換不是以達(dá)到“左高”為目的，而是無條件的，只有最后（右）節(jié)點(diǎn)例外（遞歸停止） 斜堆的合并操作 ? 我們可以用左高樹的合并算法實(shí)現(xiàn)兩個(gè)斜堆的合并。除此之外，還有一種非遞歸的算法。 ? 分割每個(gè)堆。方法是從根節(jié)點(diǎn)開始，右子樹與根節(jié)點(diǎn)分離，然后右子樹以同樣的方式分割。 ? 最后得到一個(gè)樹的集合，集合中的樹的特點(diǎn)是：其根節(jié)點(diǎn)只有左子樹或者沒有子樹。 ? 對(duì)集合中的樹，按照根節(jié)點(diǎn)的值從小到大排序。 ? 從右到左，不斷地合并最后兩個(gè)子樹，直到只剩下一棵樹。 ? 合并方法是： ? 如果倒數(shù)第二棵樹有左子樹，那么把左子樹變?yōu)橛易訕洹? ? 把最后一棵樹作為倒數(shù)第二棵樹的左子樹。 斜堆合并示例（非遞歸實(shí)現(xiàn)） 斜堆合并示例（遞歸實(shí)現(xiàn)） 斜堆的攤還分析 ? 證明斜堆合并的攤還時(shí)間為 O(logN) ? 定義：一個(gè)節(jié)點(diǎn) p，若其右子樹的后裔數(shù)至少是 p的后裔數(shù)的一般，則稱 p是重節(jié)點(diǎn)，否則稱為輕節(jié)點(diǎn) ? 位勢(shì)的選?。河衣窂缴现毓?jié)點(diǎn)的數(shù)目 斜堆的攤還分析 證明： 令 H1和 H2為兩個(gè)斜堆，節(jié)點(diǎn)數(shù)為 N1和 N2，右路徑上輕重節(jié)點(diǎn)數(shù)目分別為 l1和 h l2和 h2 若合并代價(jià)定義為右路徑上節(jié)點(diǎn)總數(shù)，則代價(jià)為 l1+h1+l2+h2 合并操作的重要特性：右路徑上的重節(jié)點(diǎn)肯定變?yōu)檩p節(jié)點(diǎn)；而輕節(jié)點(diǎn)可能不變，也可能變?yōu)橹毓?jié)點(diǎn)。 考慮最壞情況，當(dāng)然是所有輕節(jié)點(diǎn)均變?yōu)橹毓?jié)點(diǎn) 則位勢(shì)（重節(jié)點(diǎn)數(shù)）的變化為 l1+l2h1h2 平均攤還時(shí)間 =代價(jià) +位勢(shì)變化 =2(l1+l2) 現(xiàn)在只需證明 l1+l2=O(logN) 而 l1和 l2是原右路徑上的輕節(jié)點(diǎn)數(shù)目，而輕節(jié)點(diǎn)左子樹重、右子樹輕，因此 l1+l2至多為 logN1+logN2，即 O(logN) 而初始位勢(shì)為 0，始終非負(fù)，命題得證。 二項(xiàng)隊(duì)列（ binomial queue） ? 二項(xiàng)樹（ binomial tree，堆序樹）的森林 ? 二項(xiàng)樹的結(jié)構(gòu) ——遞歸構(gòu)造 –高度為 0， B0：?jiǎn)喂?jié)點(diǎn)樹 –高度為 k， Bk：由一棵二項(xiàng)樹 Bk1附接到另一棵Bk1的根上而得 二項(xiàng)樹例 二項(xiàng)樹特性 ? Bk的根節(jié)點(diǎn)的子樹為 B0、 B ...、 Bk1 ? 高度為 k的二項(xiàng)樹恰有 2k個(gè)節(jié)點(diǎn) ? d層的節(jié)點(diǎn)數(shù)目為二項(xiàng)系數(shù) ? 令二項(xiàng)樹為堆序，且每個(gè)高度僅有一棵二項(xiàng)樹，則可用二項(xiàng)隊(duì)列惟一表示任意大小的優(yōu)先隊(duì)列 ??????dk二項(xiàng)隊(duì)列表示優(yōu)先隊(duì)列例 ? 優(yōu)先隊(duì)列大小為 13： 1101，顯然每個(gè) 1對(duì)應(yīng)一棵二項(xiàng)樹， B B B0 ? 6個(gè)元素的優(yōu)先隊(duì)列表示為下圖二項(xiàng)隊(duì)列 取最小元操作 ? 取所有二項(xiàng)樹根節(jié)點(diǎn)中最小者 ? O(logN) ? 在其他操作過程中記錄最小根節(jié)點(diǎn)，則可提高到 O(1) 合并操作 ? 二進(jìn)制數(shù)相加 – 6個(gè)元素和 12個(gè)元素的二項(xiàng)隊(duì)列合并 – 110+1100——由低至高逐位相加 ? 0+0=0：兩個(gè)隊(duì)列均無 B0，合并后自然也沒有 ? 1+0=1：一個(gè)隊(duì)列有 B1，另一個(gè)沒有，合并后隊(duì)列中的 B1自然來自前者 ? 1+1=10：將兩個(gè) B2中根較大者附接到較小者，得到一個(gè) B3（進(jìn)位），結(jié)果中無 B2 ? 0+1+1=10：類似步驟三，得到一個(gè)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1