算法导论-第19章-二项堆
一、简介
二、代码
#include <iostream>using namespace std;//二项堆结点结构struct node{int key;//关键字int data;//卫星数据node *p;//指向父结点的指针，父或左兄node *child;//指向左孩子的指针node *sibling;//指向右兄弟的指针int degree;//度//初始化node(int n):key(n),p(NULL),child(NULL),sibling(NULL),degree(0){}};//二项堆结构struct Binomial_Heap{node *head;};//构造一个空的二项堆Binomial_Heap *Make_Binomial_Heap(){//分配一个对象Binomial_Heap *H = new Binomial_Heap;//初始化对象H->head = NULL;//返回对象return H;}//寻找最小关键字node* Binomial_Heap_Minimum(Binomial_Heap *H){//最小关键字一定位于某个二项树的根结点上node *x = H->head, *y = NULL;int min = 0x7fffffff;//遍历每个二项树的根结点while(x != NULL){//找出最小值if(x->key < min){min = x->key;y = x;}x = x->sibling;}return y;}//将以结点y为根的树与以结点z为根的树连接起来，使z成为y的父结点void Binomial_Link(node *y, node *z){//只是按照定义修改指针y->p = z;y->sibling = z->child;z->child = y;//增加度z->degree++;}//将H1和H2的根表合并成一个按度数的单调递增次序排列的链表//不带头结点的单调链表的合并，返回合并后的头，不需要解释node *Binomial_Heap_Merge(Binomial_Heap *H1, Binomial_Heap *H2){node *l1 = H1->head, *l2 = H2->head, *ret = NULL, *c = ret, *temp;while(l1 && l2){if(l1->degree <= l2->degree)temp = l1;elsetemp = l2;if(ret == NULL){ret = temp;c = ret;}else{c->sibling = temp;c = temp;}if(l1 == temp)l1 = l1->sibling;else l2 = l2->sibling;}if(l1 != NULL){if(ret == NULL)ret = l1;elsec->sibling = l1;}else{if(ret == NULL)ret = l2;elsec->sibling = l2;}return ret;}//将两个二项堆合并Binomial_Heap *Binomial_Heap_Union(Binomial_Heap *H1, Binomial_Heap *H2){//H是合并结点，用于输出Binomial_Heap *H = Make_Binomial_Heap();//将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 == NULL)return H;//将相等度数的根连接起来，直到每个度数至多一个根时为止//x指向当前被检查的根，prev-x指向x的前面一个根，next-x指向x的后一个根node *x = H->head, *prev_x = NULL, *next_x = x->sibling;//根据x和next-x的度数来确定是否把两个连接起来while(next_x != NULL){//情况1：度数不相等if(x->degree != next_x->degree || //情况2：x为具有相同度数的三个根中的第一个(next_x->sibling != NULL && 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-xx->sibling = next_x->sibling;//使next-x成为x的左孩子Binomial_Link(next_x, x);}//情况4：next-x->key关键字较小，x被连接到next-x上else{//将x从根表中去掉if(prev_x == NULL)//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;}return H;}//将结点x插入到二项堆H中Binomial_Heap * Binomial_Heap_Insert(Binomial_Heap *H, node *x){//构造一个临时的二项堆HH，只包含一个结点xBinomial_Heap *HH = Make_Binomial_Heap();x->p = NULL;x->child = NULL;x->sibling = NULL;x->degree = 0;HH->head = x;//将H与HH合并，同时释放HHH = Binomial_Heap_Union(H, HH);return H;}//抽取具有最小关键字的结点Binomial_Heap *Binomial_Heap_Extract_Min(Binomial_Heap *H){//find the root x with the minimum key in the root list of H, and remove x from the root list of H//最小关键字一定位于某个二项树的根结点上node *x = H->head, *y = NULL;int min;if(x == NULL){cout<<"empty"<<endl;return H;}min = x->key;//遍历每个二项树的根结点，为了删除这个结点，还需要知道x的前一个根结点while(x->sibling != NULL){//找出最小值if(x->sibling->key < min){min = x->sibling->key;y = x;}x = x->sibling;}//设待删除结点是二项树T的根，那么删除这个结点后，T变成了一个二项堆Binomial_Heap *HH = Make_Binomial_Heap();//删除结点分为两个情况，结点是二项堆中的第一个树if(y == NULL){x = H->head;HH->head = x->child;H->head = x->sibling;}//结点不是二项堆中的第一个树else{x = y->sibling;y->sibling = x->sibling;HH->head = x->child;}//原二项堆H删除二项树T后成为新二项堆H，二项树T删除根结点后变成新二项堆HH//将H和HH合并H = Binomial_Heap_Union(H, HH);return H;}//将二项堆H中的某一结点x的关键字减小为一个新值kvoid Binomial_Heap_Decrease_Key(Binomial_Heap *H, 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 != NULL && y->key < z->key){swap(y->key, z->key);swap(y->data, z->data);y = z;z = y->p;}}//删除一个关键字Binomial_Heap * Binomial_Heap_Delete(Binomial_Heap *H, node *x){//将值变为最小，升到堆顶Binomial_Heap_Decrease_Key(H, x, -0x7fffffff);//删除堆顶元素H = Binomial_Heap_Extract_Min(H);return H;}int main(){char ch;int n;//生成一个空的二项堆Binomial_Heap *H = Make_Binomial_Heap();//各种测试while(cin>>ch){switch (ch){case 'I'://插入一个元素{cin>>n;node *x = new node(n);H = Binomial_Heap_Insert(H, x);break;}case 'M'://返回最小值{node *ret = Binomial_Heap_Minimum(H);if(ret == NULL)cout<<"empty"<<endl;elsecout<<ret->key<<endl;break;}case 'K'://更改某个关键字的值，使之变小{node *ret = Binomial_Heap_Minimum(H);if(ret == NULL)cout<<"empty"<<endl;else{cin>>n;Binomial_Heap_Decrease_Key(H, ret, n);}break;}case 'E'://提取关键字最小的值并从堆中删除{H = Binomial_Heap_Extract_Min(H);break;}case 'D'://删除某个结点{node *ret = Binomial_Heap_Minimum(H);if(ret == NULL)cout<<"empty"<<endl;elseH = Binomial_Heap_Delete(H, ret);break;}}}return 0;}
三、练习
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-1
木有伪代码，直接看代码
//将H1和H2的根表合并成一个按度数的单调递增次序排列的链表//不带头结点的单调链表的合并，返回合并后的头，不需要解释node *Binomial_Heap_Merge(Binomial_Heap *H1, Binomial_Heap *H2){node *l1 = H1->head, *l2 = H2->head, *ret = NULL, *c = ret, *temp;while(l1 && l2){if(l1->degree <= l2->degree)temp = l1;elsetemp = l2;if(ret == NULL){ret = temp;c = ret;}else{c->sibling = temp;c = temp;}if(l1 == temp)l1 = l1->sibling;else l2 = l2->sibling;}if(l1 != NULL){if(ret == NULL)ret = l1;elsec->sibling = l1;}else{if(ret == NULL)ret = l2;elsec->sibling = l2;}return ret;}
19.2-5
将最小值初始化为第一个根的值
BINOMIAL-HEAP-MINIMUM(H)1 y <- NIL2 x <- head[H]3 min <- 04 while x != NIL5 do if y = NIL or key[x] < min6 then min <- key[x]7 y <- x8 x <- sibling[x]9 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
题目没看懂
18.2-8
待解决
四、思考题