Question

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;
}