datastructure.zip

  • Lucas_ftc
    了解作者
  • C/C++
    开发工具
  • 3KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2020-05-25 11:04
    上传日期
两个在STL或者ACM中常用的数据结构,二叉堆和斐波那契堆
datastructure.zip
  • Fibonacci_Heap.cpp
    5.5KB
  • binary_heap.h
    3.7KB
内容介绍
#include <cstddef> #include<vector> #include <cstring> #include <algorithm rel='nofollow' onclick='return false;'> #include <map> #include<set> #include<iterator> #include <iostream> using namespace std; const int N = 1000; const int D = 10; struct VERTEX; template <class T> class Fibonacci_Heap { private: struct Node { T key; int degree; bool mark; bool valid; Node *p, *child, *left, *right; Node(T k) : key(k), degree(0), mark(false) { p = child = NULL; left = right = this; } }; public: Node *Min; vector<Node *> root; vector<Node *> trash; typename vector<Node *>::iterator it; map<T, Node *> m; set<T> s; void Del_Tree(Node *root); void Consolidate(); void Link(Node *y, Node *x); void Cut(Node *x, Node *y); void Cascading_Cut(Node *y); public: Fibonacci_Heap(); ~Fibonacci_Heap(); int n; void Push(T x); void Push(Node *newnode); bool Empty(); T Top(); void Pop(); void Decrease_Key(T x, T k); }; template <class T> Fibonacci_Heap<T>::Fibonacci_Heap() { Min = NULL; n = 0; } template <class T> void Fibonacci_Heap<T>::Del_Tree(Node *root) { if(root -> child != NULL) { Node *ptr = root -> child; do { Del_Tree(ptr); ptr = ptr -> right; } while(ptr != root -> child); } delete root; } template <class T> Fibonacci_Heap<T>::~Fibonacci_Heap() { typename vector<Node *>::iterator del; for (del = trash.begin(); del != trash.end();del++) delete *del; } template <class T> void Fibonacci_Heap<T>::Push(T x) { //Your code Node *newone = new Node(x); trash.push_back(newone); root.push_back(newone); //if(s.find(x)==s.end()) //{ m.insert(pair<T, Node *>(x, newone)); n++; s.insert(x); //} newone->key = x; newone->child = newone->p = NULL; newone->degree=0; newone->mark = false; newone->valid = true; if(Min==NULL) { Min = newone; Min->left = Min->right = Min; } else { newone->right = Min->right; newone->left = Min; (newone->right)->left = newone; (newone->left)->right = newone; if(newone->key<Min->key) Min = newone; } } template <class T> void Fibonacci_Heap<T>::Push(Node* newnode) { newnode->valid = true; root.push_back(newnode); if(s.find(newnode->key)==s.end()) { s.insert(newnode->key); n++; m.insert(pair<T, Node *>(newnode->key, newnode)); } if (Min == NULL || Min->valid == false) { Min = newnode; Min->left = Min->right = Min; n++; return; } newnode->right = Min->right; newnode->left = Min; (newnode->right)->left = newnode; (newnode->left)->right = newnode; if(Min->valid==false || newnode->key<Min->key) Min = newnode; return; } template <class T> bool Fibonacci_Heap<T>::Empty() { return !n; } template <class T> T Fibonacci_Heap<T>::Top() { return Min->key; } template <class T> void Fibonacci_Heap<T>::Pop() { //Your code int i = 0; Node *z = Min; T mini = Min->key; if(z->child!=NULL) { Node *x = z->child; Node *nextx = x->left; for (int i = 0; i < z->degree; i++,x=nextx,nextx=x->left) { (x->left)->right=x->right; (x->right)->left = x->left; x->p = NULL; this->Push(x); } (z->left)->right = z->right; (z->right)->left = z->left; z->valid = false; Consolidate(); } else { (z->left)->right = z->right; (z->right)->left = z->left; z->valid = false; //root.remove(z); Consolidate(); } n--; m.erase(z->key); s.erase(z->key); } template <class T> void Fibonacci_Heap<T>::Consolidate() { //Your code Node *a[D]; for (int i = 0; i < D; i++) a[i] = NULL; for (it = root.begin(); it != root.end();it++) { if((*it)->valid==false) continue; Node *x = *it; int d = (*it)->degree; while(a[d]!=NULL) { Node *y = a[d]; if(x->key > y->key) swap(x, y); Link(y, x); a[d] = NULL; d++; } a[d] = x; } Min = NULL; root.empty(); for (int i = 0; i < D;i++) { if(a[i]!=NULL) { this->Push(a[i]); n--; } } } template <class T> void Fibonacci_Heap<T>::Link(Node *y, Node *x) { //Your code (y->left)->right = y->right; (y->right)->left = y->left; y->valid = false; //root.remove(y); y->p = x; y->mark = false; x->degree++; if(x->child==NULL) { x->child = y; y->left = y->right = y; } else { y->left = x->child; y->right = (x->child)->right; ((x->child)->right)->left = y; (x->child)->right = y; } } template<class T> void Fibonacci_Heap<T>::Decrease_Key(T x, T k) { //Your code if(s.find(x)==s.end()) { cout << "not find" << endl; return; } Node *point = m[x]; if (x < k) { cout << "bigger" << endl; return; } point->key = k; Node *y = point->p; if (y != NULL && point->key < y->key) { Cut(point, y); Cascading_Cut(y); } if(point->key<Min->key) Min = point; m.insert(pair<T, Node *>(k, point)); s.insert(k); } template <class T> void Fibonacci_Heap<T>::Cut(Node *x, Node *y) { //Your code (x->left)->right = x->right; (x->right)->left = x->left; x->p = NULL; Push(x); y->degree--; } template <class T> void Fibonacci_Heap<T>::Cascading_Cut(Node *y) { //Your code Node *z = y->p; if(z==NULL) return; if(y->mark==false) y->mark = true; else { Cut(y, z); Cascading_Cut(z); } }
评论
    相关推荐