# 一、概念 ### 1.可合并堆 （1）可合并堆應支持的操作 MAKE-HEAP() INSERT(H, x) MINIMUM(H) EXTRACT-MIN(H) UNION(H1, H2) （2）二項堆是一種可合并堆 ### 2.二項樹 ### （1）二項樹的定義 二項樹是Bk一種遞歸定義的有序樹 B0只包含一個結點 Bk(k>0)由兩棵二項樹B|k-1連接而成，其中一棵作為另一棵的左孩子 ### （2）二項樹Bk的性質 a.共有2^k個結點 b.樹的高度為k c.在深度i處恰有C(i, k)個結點 d.樹的度數為k，它大于任何其它結點的度；并且，如果根的子女從左到右編號為k-1, k-1, ……, 0，子女i是子樹Bi的根 ### （3）二項樹的結構 用左孩子用兄弟的方法表示二項樹 ### （4）二項樹的舉例  ### 3.二項堆 ### （1）二項堆的定義與性質 ### （2）二項堆的結構 ### （3）二項堆提供的操作 # 二、代碼 ### Binomial_Heap.h ~~~ #include <iostream> using namespace std; //二項堆結點結構 struct node { int key;//關鍵字 int data;//衛星數據 node *p;//指向父結點的指針，父或左兄 node *child;//指向左孩子的指針 node *sibling;//指向右兄弟的指針 int degree;//度 //初始化 node(int n, node *nil):key(n),p(nil),child(nil),sibling(nil),degree(0){} }; //二項堆結構 class Binomial_Heap { public: node *head; node *nil; //構造函數 Binomial_Heap(){nil = new node(-1, nil);} Binomial_Heap(node *NIL){nil = NIL;} //19.2 void Make_Binomial_Heap(); node* Binomial_Heap_Minimum(); void Binomial_Link(node *y, node *z); node *Binomial_Heap_Merge(Binomial_Heap *H1, Binomial_Heap *H2); void Binomial_Heap_Union(Binomial_Heap *H2); void Binomial_Heap_Insert(node *x); node* Binomial_Heap_Extract_Min(); void Binomial_Heap_Decrease_Key(node *x, int k); void Binomial_Heap_Delete(node *x); }; //構造一個空的二項堆 void Binomial_Heap::Make_Binomial_Heap() { //初始化對象 head = nil; } //尋找最小關鍵字 node* Binomial_Heap::Binomial_Heap_Minimum() { //最小關鍵字一定位于某個二項樹的根結點上 node *x = head, *y = nil; int min = 0x7fffffff; //遍歷每個二項樹的根結點 while(x != nil) { //找出最小值 if(x->key < min) { min = x->key; y = x; } x = x->sibling; } return y; } //將以結點y為根的樹與以結點z為根的樹連接起來，使z成為y的父結點 void Binomial_Heap::Binomial_Link(node *y, node *z) { //只是按照定義修改指針 y->p = z; y->sibling = z->child; z->child = y; //增加度 z->degree++; } //將H1和H2的根表合并成一個按度數的單調遞增次序排列的鏈表 //不帶頭結點的單調鏈表的合并，返回合并后的頭，不需要解釋 node *Binomial_Heap::Binomial_Heap_Merge(Binomial_Heap *H1, Binomial_Heap *H2) { node *l1 = H1->head, *l2 = H2->head, *ret = nil, *c = ret, *temp; while(l1 != nil && l2 != nil) { if(l1->degree <= l2->degree) temp = l1; else temp = l2; if(ret == nil) { ret = temp; c = ret; } else { c->sibling = temp; c = temp; } if(l1 == temp)l1 = l1->sibling; else l2 = l2->sibling; } if(l1 != nil) { if(ret == nil) ret = l1; else c->sibling = l1; } else { if(ret == nil) ret = l2; else c->sibling = l2; } delete H2; return ret; } //將兩個二項堆合并 void Binomial_Heap::Binomial_Heap_Union(Binomial_Heap *H2) { //H是合并結點，用于輸出 Binomial_Heap *H = new Binomial_Heap(nil); H->Make_Binomial_Heap(); Binomial_Heap *H1 = this; //將H1和H2的根表合并成一個按度數的單調遞增次序排列的鏈表，并放入H中 H->head = Binomial_Heap_Merge(H1, H2); //free the objects H1 and H2 but not the lists they point to //如果H為空，直接返回 if(H->head == nil) return; //將相等度數的根連接起來，直到每個度數至多一個根時為止 //x指向當前被檢查的根，prev-x指向x的前面一個根，next-x指向x的后一個根 node *x = H->head, *prev_x = nil, *next_x = x->sibling; //根據x和next-x的度數來確定是否把兩個連接起來 while(next_x != nil) { //情況1：度數不相等 if(x->degree != next_x->degree || //情況2：x為具有相同度數的三個根中的第一個 (next_x->sibling != nil && next_x->sibling->degree == x->degree)) { //將指針指向下一個位置 prev_x = x; x = next_x; } //情況3：x->key較小，將next-x連接到x上，將next-x從根表中去掉 else if(x->key <= next_x->key) { //去掉next-x x->sibling = next_x->sibling; //使next-x成為x的左孩子 Binomial_Link(next_x, x); } //情況4：next-x->key關鍵字較小，x被連接到next-x上 else { //將x從根表中去掉 if(prev_x == nil)//x是根表中的第一個根 H->head = next_x; else//x不是根表中的第一個根 prev_x->sibling = next_x; //使x成為next-x的最左孩子 Binomial_Link(x, next_x); //更新x以進入下一輪迭代 x = next_x; } next_x = x->sibling; } head = H->head; } //將結點x插入到二項堆H中 void Binomial_Heap::Binomial_Heap_Insert(node *x) { //構造一個臨時的二項堆HH，只包含一個結點x Binomial_Heap *HH = new Binomial_Heap; HH->Make_Binomial_Heap(); x->p = nil; x->child = nil; x->sibling = nil; x->degree = 0; HH->head = x; //將H與HH合并，同時釋放HH Binomial_Heap_Union(HH); } //抽取具有最小關鍵字的結點 node* Binomial_Heap::Binomial_Heap_Extract_Min() { //最小關鍵字一定位于某個二項樹的根結點上 node *x = head, *y = nil, *ret; int min; if(x == nil) { //cout<<"empty"<<endl; return nil; } min = x->key; //1.find the root x with the minimum key in the root list of H, //遍歷每個二項樹的根結點，為了刪除這個結點，還需要知道x的前一個根結點 while(x->sibling != nil) { //找出最小值 if(x->sibling->key < min) { min = x->sibling->key; y = x; } x = x->sibling; } ret = x; //1.and remove x from the root list of H //刪除結點分為兩個情況，結點是二項堆中的第一個樹，刪除結點后，結點的child保存到temp中 node *temp = NULL; if(y == nil) { x = head; temp = x->child; head = x->sibling; } //結點不是二項堆中的第一個樹 else { x = y->sibling; y->sibling = x->sibling; temp = x->child; } //2. //設待刪除結點是二項樹T的根，那么刪除這個結點后，T變成了一個二項堆 Binomial_Heap *HH = new Binomial_Heap(nil); HH->Make_Binomial_Heap(); //3.reverse the order of the linked list of x'childern,setting the p field of each child to NIL, and set head[HH] to point to the head of the resulting list //正常情況下，二項堆中的樹的度從小到大排。此時HH中的樹的度是從大到排的，因此要對HH中的樹做一個逆序 node *p; while(temp != nil) { p = temp->sibling; temp->sibling = HH->head; HH->head = temp; temp->p = nil; temp = p; } //4. //原二項堆H刪除二項樹T后成為新二項堆H，二項樹T刪除根結點后變成新二項堆HH //將H和HH合并 Binomial_Heap_Union(HH); return x; } //將二項堆H中的某一結點x的關鍵字減小為一個新值k void Binomial_Heap::Binomial_Heap_Decrease_Key(node *x, int k) { //引發錯誤 if(k > x->key) { cout<<"new key is greater than current key"<<endl; return ; } //與二叉最小堆中相同的方式來減小一個關鍵字，使該關鍵字在堆中冒泡上升 x->key = k; node *y = x, *z = y->p; while(z != nil && y->key < z->key) { swap(y->key, z->key); swap(y->data, z->data); y = z; z = y->p; } } //刪除一個關鍵字 void Binomial_Heap::Binomial_Heap_Delete(node *x) { //將值變為最小，升到堆頂 Binomial_Heap_Decrease_Key(x, -0x7fffffff); //刪除堆頂元素 Binomial_Heap_Extract_Min(); } ~~~ ### main.cpp ~~~ #include <iostream> using namespace std; #include "Binomial_Heap.h" int main() { char ch; int n; //生成一個空的二項堆 Binomial_Heap *H = new Binomial_Heap; H->Make_Binomial_Heap(); //各種測試 while(cin>>ch) { switch (ch) { case 'I'://插入一個元素 { cin>>n; node *x = new node(n, H->nil); H->Binomial_Heap_Insert(x); break; } case 'M'://返回最小值 { node *ret = H->Binomial_Heap_Minimum(); if(ret == H->nil) cout<<"empty"<<endl; else cout<<ret->key<<endl; break; } case 'K'://更改某個關鍵字的值，使之變小 { //因為沒有Search函數，只能對最小值的結點進行測試 node *ret = H->Binomial_Heap_Minimum(); if(ret == H->nil) cout<<"empty"<<endl; else { cin>>n; H->Binomial_Heap_Decrease_Key(ret, n); } break; } case 'E'://提取關鍵字最小的值并從堆中刪除 { H->Binomial_Heap_Extract_Min(); break; } case 'D'://刪除某個結點 { node *ret = H->Binomial_Heap_Minimum(); if(ret == H->nil) cout<<"empty"<<endl; else H->Binomial_Heap_Delete(ret); break; } } } return 0; } ~~~ # 三、練習 ### 19.1二項樹與二項堆 ~~~ 19.1-1 x不是根，則degree[sibling[x]] < degree[x] x是根，則degree[sibling[x]] > degree[x] 19.1-2 degree[p[x]] > degree[x] ~~~ ### 19.2對二項堆的操作 19.2-1 木有偽代碼，直接看代碼 ~~~ //將H1和H2的根表合并成一個按度數的單調遞增次序排列的鏈表 //不帶頭結點的單調鏈表的合并，返回合并后的頭，不需要解釋 node *Binomial_Heap::Binomial_Heap_Merge(Binomial_Heap *H1, Binomial_Heap *H2) { node *l1 = H1->head, *l2 = H2->head, *ret = nil, *c = ret, *temp; while(l1 != nil && l2 != nil) { if(l1->degree <= l2->degree) temp = l1; else temp = l2; if(ret == nil) { ret = temp; c = ret; } else { c->sibling = temp; c = temp; } if(l1 == temp)l1 = l1->sibling; else l2 = l2->sibling; } if(l1 != nil) { if(ret == nil) ret = l1; else c->sibling = l1; } else { if(ret == nil) ret = l2; else c->sibling = l2; } delete H2; return ret; } ~~~ 19.2-2  19.2-3  19.2-5 如果可以將關鍵字的值置為正無窮，BINOMIAL-HEAP-MINIMUM將無法區分二項堆為空和最小關鍵字為無窮大這兩種情況，只需在返回加以區分即可 ~~~ BINOMIAL-HEAP-MINIMUM(H) 1 y <- NIL 2 x <- head[H] 3 min <- 0x7fffffff 4 while x != NIL 5 do if key[x] < min 6 then min <- key[x] 7 y <- x 8 x <- sibling[x] 9 if min = 0x7fffffff and head[H] != NIL 10 then return head[H] 11 return y ~~~ 19.2-6 不需要表示-0x7fffffff，只要比最小值小就可以了 ~~~ BINOMIAL-HEAP-DELETE(H) 1 y <- BINOMIAL-HEAP-MINIMUM(H) 2 BINOMIAL-HEAP-DECREASE-KEY(H, x, key[y]-1) 3 BINOMIAL-HEAP-EXTRACT-MIN(H) ~~~ 19.2-7 將一個二項堆H與一個二進制數x對應，對應方式x=func(H)為： 若H中有一棵二項樹的根的度數為k，則將x的第k為置1。 （1）令一個二項堆H1有x1=func(H1)，在H1上插入一個結點后變為H2，有x2=func(H2)，則x2=x1+1 （2）令兩個二項堆H1、H2，H1、H2合并后為二項堆H3，，有x1=func(H1)、x2=func(H2)、x3=func(H3)，則x1+x2=x3 19.2-8 待解決 # 四、思考題 ### 19-1 2-3-4堆 求思路 ### 19-2 采用二項堆的最小生成樹算法 見[算法導論 19-2 采用二項堆的最小生成樹算法](http://blog.csdn.net/mishifangxiangdefeng/article/details/8184470)