【正文】 由一組只含單個(gè)結(jié)點(diǎn)的樹構(gòu)成的，并令 T為一棵具有 m個(gè)結(jié)點(diǎn)，且通過執(zhí)行一系列 WeightedUnion函數(shù)構(gòu)成的樹，則 T的高度不高于 ?log2 m? + 1。 證明： 當(dāng) m = 1，引理顯然正確。假設(shè)對(duì)于所有具有 i（ i≤m – 1）個(gè)結(jié)點(diǎn)的樹引理正確。下面需要證明對(duì)于 i = m引理也正確。 JYP 114 設(shè) T是由函數(shù) WeightedUnion構(gòu)建的，有 m個(gè)結(jié)點(diǎn)的樹。考慮最后一次并操作 union(k, j)。設(shè) a為樹 j的結(jié)點(diǎn)數(shù)，那么樹 k的結(jié)點(diǎn)數(shù)為 m – a。不失一般性，設(shè)1≤a≤m/2，則 T的根為 k。 因此， T的高度或者與原樹 k k j a ma 的相同或者比原樹 j的多一級(jí)。若是前一種情況， T的高度 ≤ ?log2 (m – a)? + 1≤?log2 m? + 1；若是后一種情況， T的高度 ≤ ?log2 a? + 2≤?log2 m? + 1。 ? JYP 115 由引理 ，如果一棵樹有 m個(gè)結(jié)點(diǎn)，則一次find操作的時(shí)間最多為 O(log m)。執(zhí)行 u –1次 union操作和 f次 find操作組成的混合序列的時(shí)間是 O(u + f log u)，因?yàn)槊靠脴涞慕Y(jié)點(diǎn)數(shù)不超過 u。當(dāng)然，初始化 n棵樹的森林需要 O(n)時(shí)間。 問題的解決方法還可以作進(jìn)一步的改進(jìn)。這次將對(duì) find操作應(yīng)用以下 坍塌規(guī)則 ：若 j是從 i到根的路徑中的結(jié)點(diǎn)，且 parent[j] ? root(i)，則將 parent[j] 設(shè)置為 root(i)。 JYP 116 函數(shù) CollapsingFind采用了坍塌規(guī)則： int Sets::CollapsingFind (int i ) { // 找到含元素 i的樹的根， //采用坍塌規(guī)則縮短從 i到根的所有結(jié)點(diǎn)到根的距離 for (int r = i。 parent[r] = 0。 r = parent[r])。 // 找到根 while ( i != r ) { int s = parent[i]。 parent[i] = r。 i = s。 } return r。 } JYP 117 對(duì) WeightedUnion和 CollapsingFind的分析： 引理 WeightedUnion和CollapsingFind完成一系列 union和 find操作的最壞情況時(shí)間復(fù)雜性。該引理用到一種增長(zhǎng)非常緩慢的函數(shù) ?(p, q)，其定義為： ?(p, q) = min{z≥1 | A(z, ?p/q?) log2 q}， p≥q≥1 其中， Ackerman函數(shù) A(i, j)定義為： A(1, j) = 2j 當(dāng) j≥1 A(i, 1) = A(i – 1, 2) 當(dāng) i≥2 A(i, j) = A(i – 1, A(i, j – 1)) 當(dāng) i, j≥2 JYP 118 A(i, j) 增長(zhǎng)非常迅速，例如， JYP 119 A(3, 1) = 16，當(dāng) q 216且 p≥q， ?(p, q)≤3。而 A(4, 1)是一個(gè)非常大的數(shù)，且在本應(yīng)用中， q是集合元素個(gè)數(shù) n， p是 n + f （ f是 find操作的次數(shù)），因此，對(duì)于任何實(shí)際可行的 p和 q， ?(p, q)≤4。 引理 ： 假設(shè)開始時(shí)森林是由一組只含單個(gè)結(jié)點(diǎn)的樹構(gòu)成的，且 u≥n/2，并令 T(f, u)為執(zhí)行 u次 union操作和 f次 find操作組成的混合序列的最長(zhǎng)時(shí)間，那么對(duì)于正常數(shù) k1和 k2，有 k1(n + f ?(f + n, n))≤T(f, u)≤k2(n + f ?(f + n, n)) JYP 120 雖然函數(shù) ?(f, u)增長(zhǎng)非常緩慢，但求解并查集問題的時(shí)間復(fù)雜性仍然不是 union和 find操作次數(shù)的線性函數(shù)。 在空間方面，每個(gè)元素需要一個(gè)結(jié)點(diǎn)。 作業(yè)： P150—26 JYP 121 在等價(jià)類問題中的應(yīng)用 等價(jià)類是集合，上一小節(jié)的方法可應(yīng)用于 等價(jià)對(duì)處理。 初始時(shí)，所有 n個(gè)元素處于由該元素獨(dú)自構(gòu)成的等價(jià)類中，即 parent[i] = –1（ 0≤i n）。 處理等價(jià)對(duì) i ? j時(shí)，首先需要確定 i和 j所在的集合。如果這是兩個(gè)不同的集合，則用它們的并取代原來的兩個(gè)集合。如果 i和 j在同一集合中，則 i ? j是冗余的。 可見，每處理一個(gè)等價(jià)對(duì)，需要完成 2個(gè) find操作和最多 1個(gè) union操作。 JYP 122 給定 n個(gè)元素和 m個(gè)等價(jià)對(duì)，需要 O(n)時(shí)間設(shè)置初始的由 n棵樹構(gòu)成的森林，接著處理 2m個(gè) find操作和最多 min{n – 1， m}個(gè) union操作。 采用 WeightedUnion和 CollapsingFind算法，處理等價(jià)對(duì)的總時(shí)間是 O(n + 2m ?(2m + n, n))。 雖然這種方法比 ，但其所需要的空間更少，且對(duì)于每個(gè)等價(jià)對(duì)，該方法所做的是在線處理。所謂“在線”，是指等價(jià)對(duì)一旦輸入即被處理，從而隨時(shí)反映等價(jià)類包含元素的狀況。 JYP 123 例 考慮 ，初始時(shí)有 12棵樹，每棵樹包含一個(gè)元素。 每處理一個(gè)等價(jià)對(duì)以后，樹的結(jié)構(gòu)變化如下： JYP 124 JYP 125 JYP 126 第 5章 堆結(jié)構(gòu) 本章學(xué)習(xí)支持優(yōu)先隊(duì)列的基本堆結(jié)構(gòu)，在后續(xù) “ 高級(jí)數(shù)據(jù)結(jié)構(gòu) ” 課程中將研究各種新型堆結(jié)構(gòu)，并用代價(jià)分?jǐn)偡椒ǚ治銎湫阅堋? JYP 127 最大堆 優(yōu)先隊(duì)列與最大堆 優(yōu)先隊(duì)列在計(jì)算機(jī)操作系統(tǒng)任務(wù)調(diào)度以及日常工作安排等領(lǐng)域具有十分廣泛的應(yīng)用。 在優(yōu)先隊(duì)列中，被刪除的是優(yōu)先級(jí)最高的元素，而在任何時(shí)刻可插入任意優(yōu)先級(jí)的元素。支持這兩種操作的數(shù)據(jù)結(jié)構(gòu)稱為 最大優(yōu)先隊(duì)列 。 如果被刪除的是優(yōu)先級(jí)最低的元素，則相應(yīng)的數(shù)據(jù)結(jié)構(gòu)稱為 最小優(yōu)先隊(duì)列 。 由于對(duì)稱性，下面只討論最大優(yōu)先級(jí)隊(duì)列。 JYP 128 最大優(yōu)先隊(duì)列可定義為如下的抽象類： template class Type class MaxPQ { public: virtual void Insert(const ElementTypeamp。) = 0。 // 純虛函數(shù) virtual ElementType* Delete(ElementTypeamp。) = 0。 }。 其中，假設(shè) ElementType已定義為 struct類型，并含有一個(gè) key數(shù)據(jù)成員。 JYP 129 用純虛函數(shù)表示 MaxPQ的原因： ? MaxPQ可用不同的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，而在未確定所 使用的數(shù)據(jù)結(jié)構(gòu)之前是不可能實(shí)現(xiàn)其操作的。 ? 任何實(shí)現(xiàn) MaxPQ的數(shù)據(jù)結(jié)構(gòu) D都必須實(shí)現(xiàn) Insert和Delete操作，這可以通過使 D成為 MaxPQ的公有派生類而得到確保。 JYP 130 假設(shè)隊(duì)列有 n個(gè)元素，表示最大優(yōu)先隊(duì)列的簡(jiǎn)單結(jié)構(gòu)： ? 無序線性表 ? 順序映射，插入操作很容易在表的尾端完成，其時(shí)間為 O(1)。刪除操作需要查找優(yōu)先級(jí)最高的元素并刪除之，需要 O(n)時(shí)間。 ? 鏈表結(jié)構(gòu)，插入操作可在表的前端完成，其時(shí)間為 O(1)。刪除操作的時(shí)間仍然為 O(n)。 ? 有序線性表 元素按優(yōu)先級(jí)非遞增次序排列，每次刪除操作的 時(shí)間為 O(1)，但每次插入操作的時(shí)間為 O(n)。 JYP 131 采用最大堆實(shí)現(xiàn)最大優(yōu)先隊(duì)列，插入和刪除操作都可以在 O(log n)時(shí)間內(nèi)完成。 定義：最大樹 是一棵樹，其中每個(gè)結(jié)點(diǎn)的 key值不小于該結(jié)點(diǎn)子女（如果存在的話）的 key值。 最大堆 既是一棵完全二叉樹，又是一棵最大樹。 JYP 132 下面是最大堆的例子： JYP 133 根據(jù)定義，最大樹的根結(jié)點(diǎn)中的元素的 key值在整個(gè)樹中是最大的。 最大堆的基本操作： （ 1） 創(chuàng)建空堆 （ 2） 將新元素插入堆中 （ 3） 從堆中刪除 key值最大的元素 JYP 134 最大堆的 ADT定義如下： template class Type class MaxHeap: public MaxPQ Type { // 對(duì)象： 由 n≥0個(gè)元素構(gòu)成的完全二叉樹和最大樹 public: MaxHeap (int sz = DefaultSize )。 // 創(chuàng)建空堆 Boolean IsFull ( )。 // 判斷堆中元素個(gè)數(shù)是否達(dá)到最大容量 void Insert (ElementTypeamp。 item)。 Boolean IsEmpty ( )。 // 判斷堆中元素個(gè)數(shù)是否為 0 ElementType* Delete(ElementTypeamp。 x )。 }。 JYP 135 由于最大堆是一棵完全二叉樹，所以可用數(shù)組heap表示。類 MaxHeap的私有數(shù)據(jù)成員定義如下： private: ElementType *heap。 int n。 // 最大堆的當(dāng)前元素個(gè)數(shù) int MaxSize。 // 堆中可容納元素的最大個(gè)數(shù) MaxHeap的構(gòu)造函數(shù)如程序如下： MaxHeap::MaxHeap (int sz = DefaultSize ) { MaxSize = sz。 n = 0。 heap = new ElementType[MaxSize+1]。 // heap[0] 不用 } JYP 136 插入操作 假設(shè)最大堆的當(dāng)前結(jié)點(diǎn)個(gè)數(shù)為 n。插入一個(gè)新元素時(shí) ? 為了保持完全二叉樹性質(zhì)，新增結(jié)點(diǎn)的編號(hào)應(yīng)為 i = n + 1。 ? 為了保持最大樹性質(zhì)，還需要比較結(jié)點(diǎn) i和其雙親的 key值。如果結(jié)點(diǎn) i的 key值大于其雙親的 key值，則將結(jié)點(diǎn) i中的元素與其雙親的元素對(duì)換，并令結(jié)點(diǎn)i的雙親成為新的結(jié)點(diǎn) i，繼續(xù)向上比較，直到結(jié)點(diǎn) i的 key值不大于其雙親的 key值或 i到達(dá)根結(jié)點(diǎn)為止。 JYP 137 前述插入過程如下所示 : JYP 138 函數(shù) Insert實(shí)現(xiàn)了最大堆插入操作： template class Type void MaxHeapType::Insert ( const ElementTypeamp。x ) { // 將元素 x 插入最大堆 if (n == MaxSize ) { HeapFull( )。 return。} n++。 for (int i = n。 i 1。) { // i==1表示已到達(dá)根結(jié)點(diǎn) if ( = heap[i/2].key) break。 // 新元素的關(guān)鍵字不大 // 于結(jié)點(diǎn) i雙親元素的關(guān)鍵字 heap[i] = heap[i/2]。 // 將雙親結(jié)點(diǎn)的元素移到結(jié)點(diǎn) i中 i/=2。 // i繼續(xù)向上 } heap[i] = x。 } JYP 139 分析： 插入過程從完全二叉樹的葉結(jié)點(diǎn)開始 ， 并向上移動(dòng) ， 最壞情況下到根為止 。 在此路徑上每一個(gè)結(jié)點(diǎn)的處理時(shí)間是 O(1)。 由于 n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為 ?log2(n+1)?， 插入函數(shù)的 for循環(huán)最多迭代 O(log n)次 。 因此 ， 插入函數(shù)的時(shí)間復(fù)雜性是 O(log n)。 JYP 140 刪除操作 從最大堆中刪除一個(gè)元素時(shí)，該元素必定在根結(jié)點(diǎn)（結(jié)點(diǎn) 1）中 ? 為了保持完全二叉樹性質(zhì)，將結(jié)點(diǎn) n中的元素暫時(shí)存放在結(jié)點(diǎn) i = 1中，最大堆的元素個(gè)數(shù)變?yōu)?n – 1。 ? 為了保持最大樹性質(zhì)，還需要比較結(jié)點(diǎn) i和其較大子女的 key值。若結(jié)點(diǎn) i的 key值小于其較大子女的key值，則將結(jié)點(diǎn) i中的元素與其較大子女的元素對(duì)換，并令結(jié)點(diǎn) i的較大子女成為新的結(jié)點(diǎn) i，繼續(xù)向下比較，直到結(jié)點(diǎn) i的 key值不小于其較大子女的 key值或 i到達(dá)葉結(jié)點(diǎn)為止。 JYP 141 前述刪除過程如下所示 : JYP 142 函數(shù) DeleteMax實(shí)現(xiàn)了最大堆刪除操作： template class Type ElementType* MaxHeapType:: DeleteMax(ElementTypeamp。x) {// 從最大堆中刪除元素 if (!n) { HeapEmpty( )。 r