菲波那契堆--一份高级数据结构的作业。实现了包括插入节点

//*************************************************************************************************
//       1.程序中用于测试的assert()已经手工修改成了注释，不会影响Debug的运行结果;
//       2.由于控制台的显示内容有限，所有测试结果均写入到根目录下的test_log.txt中，可以打开查看所有的运行信息;
//       3.当前源代码在 Visual Studio .Net 2003 中编译运行通过;
//       4.测试次数为下列宏定义（注意：必须时刻保持堆不为空，否则随机测试会报错！）
//
//*************************************************************************************************

#define MAX_NUM   1000 /*    所有单次操作的最大次数   */
#define INSERT_NUM  200  /*      随机数插入测试次数     */
#define DEL_NUM   200  /*     删除最小元素测试次数    */
#define RANDOM_DEL_NUM 20  /*     删除任一结点测试次数    */
#define RANDOM_MOD_NUM 20  /* 随机减少任一结点key测试次数 */

#include <iostream>
#include <fstream>
#include "assert.h"
#include "time.h"

using namespace std;

/* FibonacciHeap中结点的模板定义 */
template <class key_type>
class Node{
public:
 Node(key_type k, Node* min) : degree(0), parent(0), child(0), childcut(false), key(k){
  if(min){
   Insert(min);
  }else{
   right = this;
   left = this;
  }
 }

 /* 将该结点插入到Node之前 */
 void Insert(Node * node){
  if(node){
   //assert(!node->Contains(this));
   //if(!node->Contains(this)){
    right = node;
    left = node->left;
    left->right = this;
    right->left = this;
   //}
   //assert(node->Contains(this));
  }else{
   right = this;
   left = this;
  }
 }

 /* 判断 
 bool Contains(Node * node){
  if (this == node){
   return true;
  }
  Node * it = this;
  while(1){
   it = it->right;
   if (it == this)
    return false;
   if (it == node)
    break;
  }
  it = this;
  while (1){
   it = it->left;
   if (it == this)
    assert(0);
   if (it == node)
    return true;
  }
 }
 */
 
 /* 设置结点的双亲结点 */
 void SetParent(Node * p){
  parent = p;
 }
 
 /* 设置结点的KEY */
 void SetKey(key_type k){
  key = k;
 }

public:
 Node(key_type k) : degree(0), parent(0), child(0), childcut(false), key(k){
  right = this;
  left = this;
 }
 
 /* 返回指定结点的KEY */
 const key_type & GetKey() const{
  return key;
 }

private:
 template <class key_type> friend class FibonacciHeap;
 key_type key;
 Node * parent;
 Node * child;
 Node * right;
 Node * left;
 unsigned long degree;
 bool childcut;
 
};

/* FibonacciHeap的模板定义 */
template <class key_type>
class FibonacciHeap{
public:
 FibonacciHeap() : min(0), n(0){
 }

 ~FibonacciHeap(){
  Node<key_type> * node;
  while (node = GetMinimum()){
   delete node;
  }
 }

 /* 将结点插入到FibonacciHeap */
 Node<key_type> * Insert(Node<key_type> * node){
  if(min == 0){
   min = node;
  }else{
   node->Insert(min);
   if(node->GetKey() < min->GetKey()){
    min = node;
   }
  }
  ++n;
  return node;
 }
 
 /* 返回FibonacciHeap中的min所指向的结点的key */
 const key_type & Minimum(void) const{
  //assert(n>0);
  return min->GetKey();
 }

 /* 取得当前FibonacciHeap中所有结点的个数 */
 unsigned long Size(void) const{
  return n;
 }

 /* 删除最小结点 */
 Node<key_type> * GetMinimum(void){
  if(n){
   Node<key_type> * ret = min;
   if(ret){
    Node<key_type> * child = ret->child;
    if (child){
     Node<key_type> * thischild = child;
     ret->right->left = child->left;
     child->left->right = ret->right;
     ret->left->right = child;
     child->left = ret->left;
     min = ret->right;
     Consolidate();
    }else{
     ret->right->left = ret->left;
     ret->left->right = ret->right;
     min = ret->right;

     Node<key_type> * runner = min;
     Node<key_type> * LastMin = min;
     do{
      if(runner->key < min->key){
       min = runner;
      } 
      runner = runner->right;
     }while(runner != LastMin);
    }   
    --n;
   }
   return ret;
  }else{
   return 0;
  }
 }
 
 /* 删除任一结点 */
 Node<key_type> * DeleteNode(Node<key_type> * node){
  if(n){
   if(min == node){
    return GetMinimum();
   }
   if(node != node->right){
    node->right->left = node->left;
    node->left->right = node->right;   
    Node<key_type> * TempNode = node->left;
    Node<key_type> * child = node->child;
    if(child){
     min->left->right = child;
     child->left->right = min;
     min->left = child->left;
     child->left = TempNode;    
    }
   }else{
    node->parent->child = 0;
   }
   if(node->parent != 0){
    (node->parent->degree)--;
    Cut(node, node->parent);
    CascadingCut(node->parent);
   }
   Node<key_type> * runner = min;
   Node<key_type> * LastMin = min;
   do{
    if(runner->key < min->key){
     min = runner;
    } 
    runner = runner->right;
   }while(runner != LastMin);

   n--;
  }
  return node;
 }

 /* 减少任一结点的KEY值 */
 Node<key_type> * DecreaseKey(Node<key_type> * node, key_type key){
  //assert(key < node->GetKey());
  node->SetKey(key);
  Node<key_type> * parent = node->parent;
  if(node == min){
   return min;
  }
  
  if ( (parent != 0) && (key < parent->GetKey()) ){
   
   Cut(node, parent);
   CascadingCut(parent);
  }
  
  if (key < min->GetKey()){
   min = node;
  }

  return node;
 }

private:
 void Consolidate(){
  
  Node<key_type> ** A = new Node<key_type> *[n * sizeof(Node<key_type>*)];

  for (unsigned int i = 0; i != n; i++){
   A[i] = 0;
  }

  Node<key_type> * runner = min;
  
  do{
   Node<key_type> * x = runner;   
   unsigned long degree = x->degree;
   /* 合并度相同的子树 */
   while(A[degree] != 0){
    Node<key_type> * y = A[degree]; /* 数组的间址技巧 */
    if( y->key < x->key ){
     Node<key_type> * tmp = y;
     y = x;
     x = tmp; /* x为y的parent--x的key值小 */
    }
    HeapLink(y,x); /* 合并两棵子树 */
    A[degree] = 0;
    degree++;
   }
   A[degree] = x;
   runner = runner->right;
  }while(runner != min);
  for(unsigned int i = 0; i < n; i++){
   if(A[i]->key < min->key){
    min = A[i];
   }
  }
  
  delete[] A;
 }

 /* 合并子树 */
 void HeapLink(Node<key_type> * y, Node<key_type> * x){

  y->right->left = y->left;
  y->left->right = y->right;
  y->parent = x;

  if(x->child){
   y->Insert(x->child);
   y->parent = x;
  }else{