第19章-二项堆

# 一、概念 ### 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)