斐波那契堆-白红宇

斐波那契堆

阅读量：4154 次

发布时间：2019-05-25

本文共 4872 字，大约阅读时间需要 16 分钟。

以下是实现的程序

肯定可以再优化的。。

//#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;class Node{public:	int m_key;	Node *m_parent;	Node *m_left;	Node *m_right;	Node *m_child;//只要指向一个孩子结点	int m_degree;//孩子数量	bool m_mark;	Node(int key):m_key(key),m_degree(0),m_parent(NULL),m_child(NULL),m_right(this),m_left(this),m_mark(false)	{		//cout<
       
        <
        
         m_right; while (rchild!=m_child)//左右指针肯定不会为null { Node *rrchild = rchild->m_right; delete rchild; rchild = rrchild; } delete m_child; m_child = NULL; } }};class FibonacciHeap{public: //vector
         
           m_heap;//only need m_min as head Node *m_min; int m_numNode; FibonacciHeap():m_min(NULL),m_numNode(0) { } Node* Insert(int key) { Node *nd = new Node(key); ++m_numNode; Insert(nd); return nd; } void Insert(Node *nd)//将结点nd插入到root list中 { //cout<
          
           <
           
            m_right = nd; nd->m_left = nd; } else { Node *tmpRight = m_min->m_right; m_min->m_right = nd; nd->m_right = tmpRight; tmpRight->m_left=nd; nd->m_left = m_min; if(nd->m_key
            
             m_key) m_min = nd; } } void Union(FibonacciHeap &f) { Node *head = f.m_min; Node *right = head->m_right; while(right!=head) { Insert(right); right->m_parent = NULL; right = right->m_right; } Insert(head); head->m_parent = NULL; if(m_min->m_key>head->m_key) m_min = head; f.m_min = NULL;//删除f } Node *ExtractMin()//要在外面删除min { Node *minNode = m_min; if (minNode!=NULL) { Node *child = minNode->m_child; if(child!=NULL) { /*Node *right = child->m_right; while (right!=child) { right->m_parent = NULL; Node *t = right->m_right; Insert(right); right = t; } child->m_parent = NULL; Insert(child);*/ /*Node *tchild = child; vector
             
               children; while (tchild!=NULL) { tchild->m_parent = NULL; children.push_back(tchild); tchild = (tchild->m_right!=child) ?tchild->m_right :NULL; } for (int i=0;i
              
               m_right; tchild->m_parent = NULL; Insert(tchild); tchild = (next!=child) ?next:NULL; } } if(minNode == minNode->m_right) m_min = NULL; else { Node *left = minNode->m_left; Node *right = minNode->m_right; left->m_right = right; right->m_left = left; m_min = right;//随便找一个点作为min，主要是确定Head。因为min另一个作用是head Consolidate(); } minNode->m_child = NULL; minNode->m_right = minNode; minNode->m_left = minNode; --m_numNode; } return minNode; } void Consolidate()//;用数组A来检查root list上重复degree的结点;因为此时的minNode是上步中随意指定的，所以不能拿minNode 作为锚点 { vector
               
                 A(m_numNode,NULL); Node *right = m_min; if(right->m_right==right)//如果root list只有一个结点则不用处理 return; vector
                
                  rootList; rootList.push_back(m_min); for(right = m_min->m_right;right!=m_min;right = right->m_right) rootList.push_back(right); m_min = NULL;//将原root list打散 for(int i=0;i
                 
                  m_degree; while (A[d]!=NULL)//有重复 { Node *y = A[d]; if (curr->m_key>y->m_key)//要让curr所指向的节点是头 { Node *t = y; y = curr; curr = t; } Link(y,curr); A[d] = NULL;//curr的度数为degree+1,所以degree暂时没有对应的根 ++d; } A[d] = curr; } for (int i=0;i
                  
                   m_right; Node *left = child->m_left; right ->m_left = left; left->m_right = right; Node *mchild = parent->m_child; if(mchild==NULL) { parent->m_child = child; child->m_parent = parent; child->m_right = child; child->m_left = child; } else { Node *rightChild = mchild->m_right; mchild->m_right = child; child->m_right = rightChild; rightChild->m_left = child; child->m_left = mchild; } child->m_mark = false; ++parent->m_degree; } void DecreaseKey(Node *x,int key) { if(key >x->m_key) { cerr<<"new key is greater than original\n"; return; } x->m_key = key; Node *y = x->m_parent; if (y!=NULL && x->m_key 
                   
                    m_key) { Cut(x,y); CascadingCut(y); } } void CascadingCut(Node *y) { Node* parent; while ((parent = y->m_parent)!=NULL) { if(y->m_mark == false) { y->m_mark = true; break; } Cut(y,parent); y = parent; } } void Cut(Node *x,Node *y)//x是y的孩子，将x上提为root { if(x->m_right == x) { y->m_child = NULL; } else { Node *left = x->m_left; Node *right = x->m_right; y->m_child = right; left->m_right = right; right->m_left = left; } x->m_parent = NULL; x->m_mark = false; Insert(x); } void print() { Node *minNode = m_min; while (minNode!=NULL) { print(0,minNode); minNode = (minNode->m_right!=m_min)?minNode->m_right:NULL; } } void print(int level,Node *nd) { for (int i=0;i
                    
                     m_key<
                     
                      m_child; while (right!=NULL) { print(level+1,right); right = (right->m_right!=nd->m_child) ?right->m_right:NULL; } } ~FibonacciHeap() { if(m_min!=NULL) { Node *right=m_min->m_right; while (right!=m_min) { Node *rright = right->m_right; delete right; right = rright; } delete m_min; } }};int main(){ FibonacciHeap f; //f.Insert(5); int a[17] = {1,5,2,3,7,8,0,12,10,11,9,15,17,4,18,16,13}; Node *n5,*n10,*n16; for (int i=0;i<17;++i) { Node *t = f.Insert(a[i]); if(a[i] == 5) n5 = t; if(a[i] == 10) n10 = t; if(a[i]==16) n16 = t; } /*Node *t = f.ExtractMin(); cout<
                      
                       m_key<
                       
                        m_key<<"\n"; // // delete t; // //f.print(); // t = f.ExtractMin(); //} //cout<
                        
                         m_key<<"\n"; delete t; //f.print(); t = f.ExtractMin(); } return 0;}