高級數據結構

1、高級數據結構,教材：《數據結構（C++描述）》（金遠平編著，清華大學出版社）,JYP,1,代價分攤（1.5.4）,將孤立地分析一次算法調用得出的結論應用于一個ADT的相關操作序列會產生過于悲觀的結果。例1.12 整數容器Bag。class Bag { public: Bag ( int MaxSize = DefaultSize ); // 假設DefaultSize已定義 int Add (const int

2、 x ); // 將整數x加入容器中 int Delete (const int k ); // 從容器中刪除并打印k 個整數private: int top; // 指示已用空間 int *b; // 用數組b存放整數 int n; // 容量};,JYP,2,各操作的實現如下：Bag::Bag ( int MaxSize = DefaultSize ):n(Ma

3、xSize) { b = new int[n]; top = -1;} int Bag::Add (const int x) { if (top = = n-1) return 0; // 返回0表示加入失敗 else { b[++top] = x; return 1; }},JYP,3,int Bag::Delete (const int k) {

4、 if (top + 1 < k ) return 0; //容器內元素不足k個，刪除失敗 else { for (int i = 0; i < k; i++) cout << b[top – i] << “ ” ; top = top - k; return 1; }} 先分析操作成功的情況：Add(x)的時間復雜性是O(1)；

5、Delete(k)需要k個程序步，且k可能等于n，在最壞情況下其時間復雜性是O(n)；一個調用Add操作 m1次，Delete操作m2次的序列的總代價則為O(m1+ m2n)。,JYP,4,前面是常規(guī)分析的結論。進一步觀察：如果一開始容器為空，則刪除的元素不可能多于加入的元素，即 m2 次Delete操作的總代價不可能大于m1 次Add操作的總代價。因此，在最壞情況下，一個調用Add操作 m1次，Delete操作m2次的序列的總代價為O

6、(m1)。 操作失敗時，Add(x)和Delete(k) 的時間復雜性都是O(1)。因此，在操作可能失敗的情況下，一個調用Add操作 m1次，Delete操作m2次的序列的總代價為O(m1+ m2)。,JYP,5,常規(guī)分析并沒有錯，只是其推導出的總代價上界遠大于實際可得的上界。其原因是這種分析法沒有注意到連續(xù)的最壞情況刪除是不可能的。 為了取得更準確的結果，還應該度量ADT數據結構的狀態(tài)。對于每一個可能的狀態(tài)S，

7、賦予一個實數?(S)。?(S)稱為S的勢能，其選擇應使得?(S)越高，對處于S狀態(tài)的數據結構成功進行高代價操作的可能越大。 例如，將容器元素個數作為容器狀態(tài)的勢能就很合理，因為元素越多，對容器成功進行高代價操作的可能越大。,JYP,6,考慮一個由m個對ADT操作的調用構成的序列，并設ti是第i次調用的實際代價，定義第i次調用的分攤代價ai為ai = ti + ?(Si) – ?(Si-1) Si-1是第i次

8、調用開始前ADT數據結構的狀態(tài)，Si是第i次調用結束后ADT數據結構的狀態(tài)。設?的選擇使得?(Sm) ≥ ?(S0)，則,JYP,7,即，分攤代價的總和是實際代價總和的上界。 例1.12將容器元素個數作為?(S)。若操作序列始于空容器，則?(Sm) ≥ ?(S0)總是成立。下表反映了容器?(S)的典型變化情況。,JYP,8,對于Add操作，ti=1，?(Si)–?(Si-1)=1，所以ai=2；對于Delete操作，ti=

9、k，?(Si)–?(Si-1)= –k，所以ai=0。 任何一個調用Add操作 m1次，Delete操作m2次的序列的總代價為O(m1?2 + m2?0) = O(m1)。,JYP,9,可見，分攤分析法將偶爾出現的高價操作調用的代價分攤到鄰近的其它調用上，故而得名。 而且，當用分攤分析法得到的一個操作調用序列的代價總和比用常規(guī)分析法得到的代價總和小時，人們就得到了更接近實際代價的分析結果，或者說對算法時間復雜性的判斷

10、更準確了。,JYP,10,兩個字符串的最長公共子序列（2.4.3）,一個字符串的子序列通過從字符串中刪除零或多個任意位置的字符得到。兩個字符串x和y的最長公共子序列記為lcs(x, y)。例如，x = abdebcbb，y = adacbcb，則lcs(x, y)是adcbb和adbcb，如下所示：,JYP,11,問題的基本求解方法： 用?標記空串，則lcs(x, ?)= lcs(?, y) = ?。 lcs(xa

11、, ya) = lcs(x, y)a，即xa和ya的最長公共子序列由x和y的最長公共子序列后接a構成。 若xa和yb的最后一個字符不相等，則當lcs(xa, yb)不以a結尾時一定等于lcs(x, yb)，當lcs(xa, yb)不以b結尾時一定等于lcs(xa, y)。因此lcs(xa, yb)等于 lcs(x, yb)與 lcs(xa, y)中較長者。,JYP,12,由此可得計算兩個字符串最長公共子序列長度的遞歸算法lcs

12、: int String::lcs ( String y ) {// 驅動器 int n = Length( ), m = y.Length( ); return lcs( n, m, y.str );} int String::lcs (int i, int j, char *y ) {// 遞歸核心 if ( i == 0 | | j == 0) return 0; if ( str

13、[i-1] ==y[j-1] ) return ( lcs( i-1, j-1, y) + 1); return max( lcs( i-1, j, y), lcs( i, j-1, y));},JYP,13,設x的長度為n，y的長度為m，在最壞情況下lcs的時間復雜性為w(n, m)。w(n, m) =,因此，w(n, m)≥2 w(n-1, m-1)≥…≥2min(n, m)?c，即lcs的時間復雜性是指數型的。

14、 進一步可發(fā)現，lcs(i, 0)=0（0≤i≤n），lcs(0, j) =0（0≤j≤m）。lcs(i, j)的計算依賴于lcs(i–1, j–1)、lcs(i–1, j)和lcs(i, j–1)，如下圖所示：,c （c為常數）n = 0或m = 0w(n, m-1) + w(n-1, m)否則,,JYP,14,根據以上拓撲關系，可以在不用遞歸的情況下計算lcs(i, j)。算法Lcs實現了上述優(yōu)化策略，這種策略體現了動態(tài)

15、規(guī)劃的思想。算法Lcs的時間復雜性顯然是O(n?m)，這比其遞歸版有很大改進。,JYP,15,int String::Lcs ( String y ) { int n = Length( ), m = y.Length( ); int lcs[MaxN][MaxM]; // MaxN和MaxM 是已定義的常數 int i, j; for ( i = 0; i <= n; i++) lcs[i][

16、0] = 0; // 初始值 for ( j = 0; j <= m; j++) lcs[0][j] = 0;// 初始值 for ( i = 1; i <= n; i++) for ( j = 1; j <= m; j++) if ( str[i-1] ==y.str[j-1] ) lcs[i][j] = lcs[i-1][j-1] + 1;

17、 else lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]); return lcs[n][m];},JYP,16,例如，x = abdebcbb，y = adacbcb，lcs(x, y) = adbcb，改進算法的計算如下所示：,JYP,17,機場模擬（2.9）,計算機模擬（simulation）：用軟件模仿另一個系統的行為。將研究對象表示為數據結構，對象動作表示為對數據的操作，控制

18、動作的規(guī)則轉換為算法。通過更改數據的值或改變算法設置，可以觀察到計算機模擬的變化，從而使用戶能夠推導出關于實際系統行為的有用結論。在計算機處理一個對象的動作期間，其它對象和動作需等待。隊列在計算機模擬中具有重要應用。,JYP,18,簡單機場模擬：只有一個跑道。在每個時間單元，可起飛或降落一架飛機，但不可同時起降。飛機準備降落或起飛的時間是隨機的，在任一時間單元，跑道可能處于空閑、降落或起飛狀態(tài)，并且可能有一些飛機在等待降落或

19、起飛。飛機在地上等待的代價比在空中等待的小，只有在沒有飛機等待降落的情況下才允許飛機起飛。當出現隊列滿的情況時，則拒絕為新到達的飛機服務。,JYP,19,需要兩個隊列l(wèi)anding和takeoff。飛機可描述為：struct plane { int id;// 編號 int tm;// 到達隊列時間};飛機的動作為：enum action { ARRIVE, DEPART };,JYP,20,模擬運行: 時間

20、單元:1 — endtime，并產生關于機場行為的重要統計信息，如處理的飛機數量，平均等待時間，被拒絕服務飛機的數量等。 采用基于泊松分布的隨機整數決定在每個時間單元有多少架新飛機需要降落或起飛。 假設在10個時間單元中到達的飛機數分別是：2，0，0，1，4，1，0，0，0，1，那么每個時間單元的平均到達數是0.9。,JYP,21,一個非負整數序列滿足給定期望值v的泊松分布意味著，對于該序列的一段足夠長的子序列，其中整數的平均值接近

21、v。 在模擬中還需要建立新到達飛機的數據，處理被拒絕服務的飛機，起飛、降落飛機，處理機場空閑和總結模擬結果。 下面是機場模擬類定義：,JYP,22,class AirportSimulation {// 機場模擬。一個時間單元 = 起飛或降落的時間public: AirportSimulation( );// 構造函數 void RunSimulation( );// 模擬運行private:

22、 Queue landing(6);// 等待降落飛機隊列，假設用環(huán)// 型隊列，實際長度為5 Queue takeoff(6);// 等待起飛飛機隊列，同上 double expectarrive; //一個時間單元內期望到達降落飛機數 double expectdepart; //一個時間單元內期望到達起飛飛機數 int curtime;// 當前時間 int endtime;

23、 // 模擬時間單元數 int idletime ; // 跑道空閑時間單元數 int landwait ; // 降落飛機的總等待時間,JYP,23,int nland ; // 降落的飛機數 int nplanes; // 處理的飛機數 int nrefuse; // 拒絕服務的飛機數 int ntakeoff; // 起飛的飛機數 void Randomize( );

24、// 設置隨機數種子 int PoissionRandom(double& expectvalue); // 根據泊松分布和給定期望值生成隨機非負整數 plane* NewPlane(plane& p, action kind); // 建立新飛機的數據項 void Refuse(plane& p, action kind); // 拒絕服務 void Land(p

25、lane& p); // 降落飛機 void Fly(plane& p); // 起飛飛機 void Idle( ); // 處理空閑時間單元 void Conclude( ); // 總結模擬結果};,JYP,24,構造函數初始化各變量，如下所示：AirportSimulation::AirportSimulation( ) {// 構造函數 Boolean ok

26、; cout > endtime; idletime = landwait = nland = nplanes = 0; nrefuse = ntakeoff = takoffwait = 0; // 初值 Randomize( ); // 設置隨機數種子 do { cout > expectarrive; cout > expectdepart;,JYP,

27、25,if (expectarrive 1.0) { cout << “機場將飽和！請重新輸入?！?lt;< endl; ok = FALSE; } else ok = TRUE; } while (ok == FALSE);},JYP,26,RunSimulation( )是模擬運行

28、的主控程序：void AirportSimulation::RunSimulation( ) { int pri; // 偽隨機整數 plane p; for (curtime = 1; curtime <= endtime; curtime++) { cout << “時間單元” << curtime << “：” ; pri = Po

29、issionRandom(expectarrive); for (int i =1; i <= pri; i++) { //處理新到達準備降落的飛機 p = *NewPlane(p, ARRIVE); if (landing.IsFull( )) Refuse(p, ARRIVE); else landing.Add(p); }

30、 pri = PoissionRandom(expectdepart);,JYP,27,for (int i =1; i <= pri; i++) { //處理新到達準備起飛的飛機 p = *NewPlane(p, DEPART); if (takeoff.IsFull( )) Refuse(p, DEPART); else takeoff.Add(p);

31、 } if (!landing.IsEmpty( )) { // 降落飛機 p = *landing.Delete(p); Land(p); } else if (!takeoff.IsEmpty( )) {// 起飛飛機 p = *takeoff.Delete(p); Fly(p);

32、 } else Idle( );// 處理空閑時間單元 } Conclude( );// 總結模擬結果},JYP,28,用庫函數srand和rand生成隨機數，并用時鐘設置隨機種子，以增強隨機性：void AirportSimulation::Randomize( ) { srand((unsigned int) (time(NULL)%10000));}

33、 庫函數time返回自格林威治時間1970年1月1日00:00:00 至今經歷的秒數。這使得每次模擬運行隨機數起點都不同。 rand按照均勻分布生成隨機數，還需要轉化為適合機場模擬的泊松分布隨機數。下面直接給出根據泊松分布和給定期望值生成偽隨機整數的算法（其數學推導略） ：,JYP,29,int AirportSimulation::PoissionRandom(double& expectvalue) { in

34、t n = 0;// 循環(huán)計數 double limit; // e-v, 其中，v是期望值 double x; // 偽隨機數 limit = exp(-expectvalue); x = rand( ) / (double) INT_MAX; // rand( )生成0到INT_MAX之間的整數, x在0和1之間 while (x > limit) { n++;

35、 x *= rand( ) / (double) INT_MAX; } return n;},JYP,30,建立新飛機的數據項由函數NewPlane實現：plane* AirportSimulation::NewPlane(plane& p, action kind) { nplanes++;// 飛機總數加1 p.id = nplanes; p.tm = curtime;

36、switch (kind) { case ARRIVE: cout << “飛機” << nplanes << “準備降落?！?<< endl; break; case DEPART: cout << “飛機” << nplanes << “準備起飛?！?<

37、;< endl; break; } return &p;},JYP,31,處理被拒絕的飛機由函數Refuse實現:void AirportSimulation::Refuse(plane& p, action kind) { switch (kind) { case ARRIVE: cout << “引導飛機” &

38、lt;< p.id << “到其它機場降落?！?<< endl; break; case DEPART: cout << “告訴飛機” << p.id << “等一會兒再試?！?<< endl;

39、 break; } nrefuse++;// 被拒絕飛機總數加1},JYP,32,處理飛機降落由函數Land實現：void AirportSimulation::Land(plane& p) { int wait; wait = curtime – p.tm; cout << “飛機” << p.id << “降落，該機等待時間：”

40、 << wait << “?！?lt;< endl; nland++;// 降落飛機總數加1 landwait += wait;// 累加總降落等待時間},JYP,33,處理飛機起飛由函數Fly實現：void AirportSimulation::Fly(plane& p) { int wait = curtime – p.tm; cout &

41、lt;< “飛機” << p.id << “起飛，該機等待時間：” << wait << “?！?lt;< endl; ntakeoff++;// 起飛飛機總數加1 takeoffwait += wait;// 累加總起飛等待時間},JYP,34,處理機場空閑由函數Idle實現：void AirportSimulation::

42、Idle( ) { cout << “跑道空閑?！?<< endl; idletime++;// 跑道空閑時間加1} 總結模擬結果由函數Conclude實現：void AirportSimulation::Conclude( ) { cout << “總模擬時間單元數：” << endtime << endl; cout <

43、< “總共處理的飛機數：” << nplanes << endl; cout << “降落飛機總數：” << nland << endl; cout << “起飛飛機總數：” << ntakeoff << endl;,JYP,35,cout 0) cout 0) cout 0) cout << “起飛平

44、均等待時間：” << (double) takeoffwait / ntakeoff << endl;},JYP,36,可通過下列程序模擬運行：#include “common.h”#include “simdefs.h”// 存放模擬類定義及相關函數實現void main( ) { AirportSimulation s; s.RunSimulation( );

45、},JYP,37,模擬過程產生的數據如下：請輸入模擬時間單元數：30請輸入一個時間單元內期望到達降落飛機數：0.47請輸入一個時間單元內期望到達起飛飛機數：0.47時間單元1：飛機1準備降落。 飛機1降落，該機等待時間：0。時間單元2：跑道空閑。時間單元3：飛機2準備降落。 飛機3準備降落。 飛機2降落，該機等待時間：0。時間單元4： 飛機3降落，該機等待時間：1。,JYP,38,時間單元5：飛機

46、4準備降落。 飛機5準備降落。 飛機6準備起飛。 飛機7準備起飛。 飛機4降落，該機等待時間：0。時間單元6：飛機8準備起飛。 飛機5降落，該機等待時間：1。時間單元7：飛機9準備起飛。 飛機10準備起飛。 飛機6起飛，該機等待時間：2。時間單元8： 飛機7起飛，該機等待時間：3。時間單元9： 飛機8起飛，該機等待時間：3。,JYP,39,時間單元10：飛機11準備降落。

47、 飛機11降落，該機等待時間：0。時間單元11：飛機12準備起飛。 飛機9起飛，該機等待時間：4。時間單元12：飛機13準備降落。 飛機14準備降落。 飛機13降落，該機等待時間：0。時間單元13： 飛機14降落，該機等待時間：1。時間單元14： 飛機10起飛，該機等待時間：7。時間單元15： 飛機15準備降落。 飛機16準備起飛。 飛機17準備起飛。

48、 飛機15降落，該機等待時間：0。,JYP,40,時間單元16：飛機18準備降落。 飛機19準備降落。 飛機20準備起飛。 飛機21準備起飛。 飛機18降落，該機等待時間：0。時間單元17： 飛機22準備降落。 飛機19降落，該機等待時間：1。時間單元18： 飛機23準備起飛。 告訴飛機23等一會兒再試。 飛機22降落，該機等待時間：

49、1。,JYP,41,時間單元19： 飛機24準備降落。 飛機25準備降落。 飛機26準備降落。 飛機27準備起飛。 告訴飛機27等一會兒再試。 飛機24降落，該機等待時間：0。時間單元20： 飛機28準備降落。 飛機29準備降落。 飛機30準備降落。 飛機31準備降落。 引導飛機31到其它機場降落。

50、 飛機25降落，該機等待時間：1。,JYP,42,時間單元21：飛機32準備降落。 飛機33準備起飛。 告訴飛機33等一會兒再試。 飛機26降落，該機等待時間：2。時間單元22：飛機28降落，該機等待時間：2。時間單元23：飛機29降落，該機等待時間：3。時間單元24：飛機34準備起飛。 告訴飛機34等一會兒再試。 飛機30降落，該機等待時間：4。,JYP,43,時間單元

51、25：飛機35準備起飛。 告訴飛機35等一會兒再試。 飛機36準備起飛。 告訴飛機36等一會兒再試。 飛機32降落，該機等待時間：4。時間單元26：飛機37準備起飛。 告訴飛機37等一會兒再試。 飛機12起飛，該機等待時間：15。時間單元27：飛機16起飛，該機等待時間：12。時間單元28：飛機17起飛，該機等待時間：13。時間單元29：飛機20起飛，該機等待時間

52、：13。,JYP,44,時間單元30：飛機38準備起飛。 飛機21起飛，該機等待時間：14。總模擬時間單元數：30總共處理的飛機數：38降落飛機總數：19起飛飛機總數：10拒絕服務的飛機總數：8隊列中剩余的準備降落飛機數：0 隊列中剩余的準備起飛飛機數：1跑道空閑時間百分比：3.33降落平均等待時間：1.11起飛平均等待時間：8.60,JYP,45,二叉樹計數(4.9),當n = 0或1時，只有一棵二叉樹

53、。 當n = 2，存在2棵不同（結構）的二叉樹：,JYP,46,而當n = 3，則存在5棵不同的二叉樹：,那么，具有n個結點的不同二叉樹究竟有多少呢？,JYP,47,不失一般性，將樹的n個結點編號為1到n。假設一棵二叉樹的前序序列為1 2 3 4 5 6 7 8 9且其中序序列為2 3 1 5 4 7 8 6 9，則通過這對序列可以唯一確定一棵二叉樹。 為了構造相應的二叉樹，可找出前序第一個結點，即1。于是，結點1是

54、樹根，中序序列中所有在1之前的結點（2 3）屬于左子樹，其余結點（5 4 7 8 6 9）屬于右子樹。,JYP,48,這一步構造如下所示：,JYP,49,接著，可根據前序序列2 3和中序序列2 3構造左子樹。顯然，結點2是樹根。由于在中序序列中，結點2之前無結點，所以其左子樹為空，結點3是其右子樹，如下圖所示：,JYP,50,如此繼續(xù)，最終可唯一地構造下圖所示的二叉樹：,JYP,51,一般地，我們可以設計算法，根據二叉樹的前序/中序序列

55、對構造該樹。 可以證明，每一棵二叉樹都有唯一的前序/中序序列對。 如果樹中結點按前序編號，即樹的前序序列為1, 2, …, n，則由上討論可知，不同的二叉樹定義不同的中序序列。 因此，不同的二叉樹個數等于從前序序列為1, 2, …, n的二叉樹可產生的不同的中序序列的個數。,JYP,52,設bn是具有n個結點的不同二叉樹的個數。bn實際上是按以下方式形成的各種可能的二叉樹個數之和：一個根和兩個結點數分別為i

56、和n–i–1的子樹(0≤i < n)，如下所示：,JYP,53,對于每一個i，存在bi bn-i-1棵不同的樹，因此有,(4.3),為了用n表示bn，必須求解遞歸方程(4.3)。設,(4.4),JYP,54,B(x)是二叉樹個數的生成函數。由于,JYP,55,即 x B2(x) – B(x) + 1 = 0,JYP,56,解此一元二次方程，并注意B(0) = b0 = 1（等式(4.3)），可得,利用二項式公式展開(1 –

57、 4x)1/2得到,JYP,57,令n = m + 1，可得,(4.5),JYP,58,比較等式(4.4) 和(4.5)，并注意bn是B(x)中xn的系數，可得,JYP,59,JYP,60,最小最大堆 (5.2),5.2.1 雙端優(yōu)先隊列與最小最大堆 雙端優(yōu)先隊列是一種支持下列操作的數據結構：（1） 插入一個具有任意key值的元素（2） 刪除key值最大的元素（3） 刪除key值最小的元素 當只需要支持兩個刪除

58、操作之一時，可采用前一節(jié)的最小堆或最大堆。而最小最大堆可支持以上全部操作。,JYP,61,雙端優(yōu)先隊列可定義為如下的抽象類：template class DEPQ {public: virtual void Insert(const Element&) = 0; virtual Element* DeleteMax(Element&) = 0; virtual Element* DeleteMin

59、(Element&) = 0;};其中，假設Element含有一個key數據成員。,JYP,62,定義：最小最大堆是一棵完全二叉樹，且其中每個元素有一個key數據成員。樹的各層交替為最小層和最大層。根結點在最小層。設x是最小最大堆的任意結點。若x在最小（最大）層上，則x中的元素的key值在以x為根的子樹的所有元素中是最小（最大）的。位于最小（最大）層的結點稱為最?。ㄗ畲螅┙Y點。,JYP,63,下面是一個具有12個元素的最小最

60、大堆，其中最大層的結點用粗體字表示：,JYP,64,最小最大堆定義為DEPQ的派生類，以確保實現DEPQ的三個操作。template class MinMaxHeap: public DEPQ {public: MinMaxHeap (const int); // 構造函數 ~MinMaxHeap ( ); // 析構函數 void Insert (const Element&);

61、 Element* DeleteMax(Element& x ); Element* DeleteMin(Element& x );private: Element *h; int n; // 最小最大堆的當前元素個數 int MaxSize;// 堆中可容納元素的最大個數,JYP,65,// 其它用于實現最小最大堆的私有數據成員 …};template // 構造函數定義M

62、inMaxHeap::MinMaxHeap (const int sz = DefaultHeapSize) : MaxSize(sz), n(0) {h = new Element[MaxSize+1]; // h[0] 不用},JYP,66,5.2.2 插入操作,假設將key為5的元素插入圖5.4的最小最大堆。插入后的堆有13個元素，其形狀如下圖：,JYP,67,最小最大堆的插入算法也需要沿從新結點j到根的路徑比較key值。

63、 比較結點j的key值5和j的雙親的key值10，由于存放key值10的結點位于最小層，且5 < 10，所以5一定小于所有從j到根的路徑中位于最大層的結點的key值。 為了保持最小最大堆的性質，只需要檢查從j到根的路徑中的最小結點即可。首先，將key為10的元素移到結點j。接著，將key為7的元素移到10的原來位置。最后，將key為5的元素插入根結點。,JYP,68,由此形成的最小最大堆如下圖，圓周加粗的結點內容

64、在插入過程修改過：,JYP,69,再假設將key為80的元素插入圖5.4所示的最小最大堆。插入后的堆有13個元素，其形狀也與前面相同。 由于存放key值10的結點位于最小層，且10 < 80，所以80一定大于所有從j到根的路徑中位于最小層的結點的key值。 為了保持最小最大堆的性質，只需要檢查從j到根的路徑中的最大結點即可。圖5.4中只有一個這樣的結點，其元素的key值為40，將該元素移到結點j，并將key為8

65、0的新元素插入key為40的元素原來的結點。,JYP,70,由此形成的最小最大堆如下圖：,JYP,71,成員函數Insert實現了上述過程，其中又用到私有成員函數VerifyMax，VerifyMin 和level。template void MinMaxHeap::Insert(const Element&x ) { if (n == MaxSize ) { MinMaxFull( ); return;} n+

66、+; int p = n/2; // p是新結點的雙親 if (!p) {h[1] = x; return;} // 插入初始時為空的堆 switch (level(p)) { case MIN: if (x.key < h[p].key) { // 沿著最小層檢查 h[n]=h[p]; VerifyMin(p, x);

67、 },JYP,72,else VerifyMax(n, x); // 沿著最大層檢查 break; case MAX: if (x.key > h[p].key) { // 沿著最大層檢查 h[n]=h[p]; VerifyMax(p, x); } else VerifyMin(n, x

68、); // 沿著最小層檢查 } // switch結束} // Insert結束,JYP,73,函數level確定一個結點是位于最小最大堆的最小層，還是位于最大層。根據引理4.2，當?log2(j + 1)?為偶數時，結點j位于最大層，否則位于最小層。 函數VerifyMax從最大結點i開始，沿著從結點i到最小最大堆的根的路徑檢查最大結點，查找插入元素x的正確結點。在查找過程中，key值小于x.key的元素被移

69、到下一個最大層。,JYP,74,template void MinMaxHeap::VerifyMax (int i, const Element&x ) { // 沿著從最大結點i // 到根結點的路徑檢查最大結點，將x插入正確位置 for (int gp = i/4; gp && (x.key > h[gp].key); gp /=4) { // gp是 i的祖父

70、 h[i] = h[gp];// 將h[gp]移到h[i] i = gp; } h[i] = x; // 將x插入結點i},JYP,75,函數VerifyMin與VerifyMax類似，所不同的是，前者從最小結點i開始，沿著從結點i到根的路徑檢查最小結點，將元素x插入正確位置。 分析：由于n個元素的最小最大堆有O(log n)層，成員函數Insert的時間復雜性是O(log n)。,J