`
kmplayer
  • 浏览: 509818 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

斐波那契堆

J#
阅读更多
学习的地方:
http://en.wikipedia.org/wiki/Talk:Fibonacci_heap
http://jicheng.ycool.com/post.2380567.html
1,先贴个代码: 
#include <iostream>
using namespace std;


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct element
{
    int key;
};

struct fiboheap
{
    element data;
    fiboheap *child;
    fiboheap *left_link;
    fiboheap *right_link;
    int degree;
    bool child_cut;
    fiboheap *parent;
};
#define TREELEN 8

void join_min_trees(fiboheap *a, fiboheap *b)
{
    if(a->data.key < b->data.key)
    {
        if(a->child == NULL)
        {
            a->right_link = a->left_link = a;
            b->right_link = b->left_link = b;
        }
        else
        {
            fiboheap *temp = a->child->left_link;
            a->child->left_link = b;
            b->right_link = a->child;
            b->left_link = temp;
            temp->right_link = b;
        }
        a->child = b;
        a->degree++;
        b->parent = a;
        b->child_cut = true;
    }
    else 
    {
        if(b->child == NULL) 
        {
            a->right_link = a->left_link = a;
            b->right_link = b->left_link = b;
        } 
        else 
        {
            fiboheap *temp = b->child->left_link;
            b->child->left_link = a;
            a->right_link = b->child;
            a->left_link = temp;
            temp->right_link = a;
        }
        b->child = a;
        b->degree++;
        a->parent = b;
        a->child_cut = true;
        a = b;
    }
}
//寻找于所给值相同的节点
fiboheap *find(fiboheap *a, int key)
{
    fiboheap *p = a;
    do {
        if(p->data.key == key) 
        {
            return p;
        }
        if (p->child != NULL) 
        {
            fiboheap *q = find(p->child, key);
            if(q != NULL) return q;
        }
        p = p->right_link;
    } while(p != a);
    return NULL;
}
element del_min(fiboheap*&);
//删除与所给值相同的节点
void del_fix(fiboheap *&a, int key)
{
        fiboheap *p = find(a, key);
        if(p == NULL) 
        {//堆中没有与所给值相同的节点
            return;
        } 
        else if(p == a) 
        {//正好要删除最小值
                del_min(p);
        } else if(p->child_cut == false) {//删除处于顶点节点所组成的双向循环链表中
                fiboheap *i = p->left_link;
                fiboheap *j = p->right_link;
                fiboheap *k = p->child;
                fiboheap *m = k->left_link;
                i->right_link = k;
                k->left_link = i;
                m->right_link = j;
                j->left_link = m;
                k->parent = NULL;
                k->child_cut = false;
                free(p);
        } 
        else//删除不在由顶点节点所组成的双向循环链表中 
        {
                if(p->degree == 0)//节点下面没有子节点了 
                {
                        p->parent->child = NULL;
                        p->parent->degree--;
                } else//节点下面还有子节点 
                {
                        fiboheap *p_left = p->left_link;
                        fiboheap *p_right = p->right_link;
                        p_left->right_link = p_right;
                        p_right->left_link = p_left;
                        p->parent->child = p_right;
                        p->parent->degree--;
                        fiboheap *child = p->child;
                        child->parent = NULL;
                        child->child_cut = false;
                        fiboheap *child_left = child->left_link;
                        fiboheap *a_right = a->right_link;
                        a->right_link = child;
                        child->left_link = a;
                        child_left->right_link = a_right;
                        a_right->left_link = child_left;
                }
                //级联剪枝操作
                fiboheap *del_node = p;
                p = p->parent;
                while(p->child_cut != false) {
                        fiboheap *parent = p->parent;
                        p->parent = NULL;
                        fiboheap *p_left = p->left_link;
                        fiboheap *p_right = p->right_link;
                        p_left->right_link = p_right;
                        p_right->left_link = p_left;
                        p->child_cut = false;
                        parent->child = p_right;
                        parent->degree--;
                        fiboheap *a_right = a->right_link;
                        a->right_link = p;
                        p->right_link = a_right;
                        p->left_link = a;
                        a_right->left_link = p;
                        p = parent;
                }
                free(del_node);
        }
}
//关键值减值操作
void decrease(fiboheap *&a, int key, int value)
{
        fiboheap *p = find(a, key);
        if(p == a) {//无对应的节点
                p->data.key -= value;
        } else if(p->child == false) {//所操作节点处于顶点节点组成的双向循环链表中
                p->data.key -= value;
                if(p->data.key < a->data.key) {
                        a = p;
                }
        } else {
                fiboheap *q = p;
                p->data.key -= value;
                //级联剪枝操作
                while(p->child_cut != false) {
                        fiboheap *parent = p->parent;
                        p->parent = NULL;
                        fiboheap *p_left = p->left_link;
                        fiboheap *p_right = p->right_link;
                        p_left->right_link = p_right;
                        p_right->left_link = p_left;
                        p->child_cut = false;
                        parent->child = p_right;
                        parent->degree--;
                        fiboheap *a_right = a->right_link;
                        a->right_link = p;
                        p->right_link = a_right;
                        p->left_link = a;
                        a_right->left_link = p;
                        p = parent;
                }
                if(q->data.key < a->data.key) {
                        a = q;
                }
        }
}
element del_min(fiboheap *&a)
{
        element temp = a->data;
        fiboheap *tree[TREELEN];
        for(int i=0; i<TREELEN; ++i) {
                tree[i] = NULL;
        }
        fiboheap *p1, *p2;
        if(a->left_link != a) {
                p1 = a->left_link;
                p1->right_link = a->right_link;
                a->right_link->left_link = p1;
        }
        p2 = a->child;
        fiboheap *m1 = p1;
        fiboheap *m2 = p2;
        do {
                if(m1 == NULL) break;
//              printf("%d\n", m1->data.key);
                int degree;
                fiboheap *w = m1->right_link;
                for(degree=m1->degree; tree[degree]; ++degree) {
                        join_min_trees(m1, tree[degree]);
                        tree[degree] = NULL;
                }
                tree[degree] = m1;
                m1 = w;
        } while (m1 != p1);
        do {
                if(m2 == NULL) break;
//              printf("%d\n", m2->data.key);
                int degree;
                fiboheap *w = m2->right_link;
                for(degree=m2->degree; tree[degree]; ++degree) {
                        join_min_trees(m2, tree[degree]);
                        tree[degree] = NULL;
                }
                tree[degree] = m2;
                m2 = w;
        } while (m2 != p2);
        int k = 0;
        for(int i=0; i<TREELEN; ++i) {
                if(tree[i] == NULL) continue;
                k++;
                if(k == 1) {
                        tree[i]->right_link = tree[i]->left_link = tree[i];
                        a = tree[i];
                } else if(k > 1) {
                        fiboheap *temp = a->right_link;
                        a->right_link = tree[i];
                        temp->left_link = tree[i];
                        tree[i]->right_link = temp;
                        tree[i]->left_link = a;
                        if(a->data.key > tree[i]->data.key) a = tree[i];
                }
        }
        return temp;
}
void insert(fiboheap *&a, fiboheap *b)
{
        if(a == NULL) {
                a = b;
                return;
        }
        fiboheap *temp = a->right_link;
        a->right_link = b;
        b->right_link = temp;
        temp->left_link = b;
        b->left_link = a;
        if(a->data.key > b->data.key) {
                a = b;
        }
}
void merge(fiboheap *&a, fiboheap *b)
{
        if(a == NULL) {
                a = b;
                return;
        }
        fiboheap *p1 = a->right_link;
        fiboheap *p2 = b->left_link;
        a->right_link = b;
        b->left_link = a;
        p1->left_link = p2;
        p2->right_link = p1;
        if(a->data.key > b->data.key) {
                a = b;
        }
}
void traverse(fiboheap *a)
{
        fiboheap *p = a;
        do {
                printf("%4d%4d%4d", p->data.key, p->degree, p->child_cut);
                if(p->child != NULL) printf(" 1 ");
                else printf(" 0 ");
                if(p->parent != NULL) printf(" 1 ");
                else printf(" 0 ");
                printf("\n");
                if (p->child != NULL) {
                        traverse(p->child);
                }
                p = p->right_link;
        } while(p != a);
}
int main()
{
        fiboheap *a = NULL;
        for(int i=1; i<=8; ++i) {
                fiboheap *p = new fiboheap;
                p->right_link = p->left_link = p;
                p->child = p->parent = NULL;
                p->data.key = i;
                p->degree = 0;
                p->child_cut = false;
                insert(a, p);
        }
        fiboheap *b = NULL;
        for(int i=9; i<=17; ++i) {
                fiboheap *p = new fiboheap;
                p->right_link = p->left_link = p;
                p->child = p->parent = NULL;
                p->data.key = i;
                p->degree = 0;
                p->child_cut = false;
                insert(b, p);
        }
        del_min(a);
        del_min(b);
        merge(a, b);
        traverse(a);
        printf("\n");
        decrease(a, 13, 15);
//      del_fix(a, 13);
        traverse(a);
}












/*
class Point    //Point 类的声明
{
public:    //外部接口
      Point(int xx=0, int yy=0) {X=xx;Y=yy;}    //构造函数
      Point(Point &p);    //拷贝构造函数
      int GetX() {return X;}
      int GetY() {return Y;}
private:    //私有数据
      int X,Y;
};

//成员函数的实现
Point::Point(Point &p)
{
      X=p.X;
      Y=p.Y;
      cout<<"拷贝构造函数被调用"<<endl;
}

//形参为Point类对象的函数
void fun1(Point p)
{    cout<<p.GetX()<<endl;
}

//返回值为Point类对象的函数
Point fun2()
{
      Point A(1,2);
      return A;
}

//主程序
int main()
{
      Point A(4,5);    //第一个对象A
      Point B(A);                  //情况一，用A初始化B。第一次调用拷贝构造函数
      cout<<B.GetX()<<endl;
      fun1(B);  //情况二，对象B作为fun1的实参。第二次调用拷贝构造函数
//      B = fun2();  //情况三，函数的返回值是类对象，函数返回时，调用拷贝构造函数
           cout<<B.GetX()<<endl;

      return 0;
}
*/
分享到：
| Sunday算法
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    二叉堆（最小堆）+二项堆+斐波那契堆

    二叉堆、二项堆和斐波那契堆是数据结构中的重要概念，它们都是堆数据结构的不同变体，主要用于高效地实现某些特定操作，如查找最大或最小元素、优先队列以及各种排序算法。在C++编程语言中，理解和实现这些堆结构...

    斐波那契堆（fibonacci）

    2. 删除最小元素：斐波那契堆通过“瀑布修剪”（Fibonacci Heap Deletion）策略来优化这个操作。当删除最小元素时，会将所有与其相邻的子节点提升到其位置，这个过程可能引发树的重构，但总体上保证了操作的时间...

    斐波那契堆ppt（中文）

    斐波那契堆是一种高效的优先队列数据结构，主要用于图的最小生成树算法，如Prim算法和Kruskal算法，以及Dijkstra最短路径算法。它由计算机科学家Frederick S.~Tarjan提出，其设计灵感来源于自然界中的斐波那契数列。...

    斐波那契堆python实现

    斐波那契堆的python实现(优先队列)，实现内容：merge(H), insert(v), find_min() # extractMin(), coalesce_step(), updateMin() # decreaseKey(v,k), delete(v)

    斐波那契堆C++实现

    斐波那契堆是一种高效的优先队列数据结构，主要用于图论中的最短路径算法，如Dijkstra算法和Prim算法。它的设计灵感来源于自然界中的斐波那契数列，通过巧妙地组织节点，使得插入、删除最小元素以及合并操作的时间...

    算法导论斐波那契堆（C#,C++）

    斐波那契堆是一种高效的优先队列数据结构，它在计算机科学中，特别是在算法和图论领域具有重要的应用。在《算法导论》一书中，斐波那契堆被广泛讨论，因为它在解决诸如最短路径、最小生成树等算法问题时能提供高效的...

    FibHeapDemo2.rar，斐波那契堆的C#实现

    斐波那契堆（Fibonacci Heap）是一种高级的数据结构，常用于图的最短路径算法，如Dijkstra算法和Floyd-Warshall算法，以及优先队列等场景。它是基于树的堆结构，由多个堆节点组成，每个节点包含一个键值、一个指向其...

    斐波那契堆C++

    从提供的文件"www.pudn.com.txt"和"FibonacciHeap"来看，可能包含了关于斐波那契堆的C++代码实现。具体实现细节可能包括类定义、成员函数（如insert、delete_min、decrease_key等）以及相应的辅助函数。 总的来说...

    斐波那契堆（Fibonacci Heap）

    斐波那契堆（Fibonacci Heap）是一种高级的数据结构，主要用于解决图的最短路径问题、优先队列等需要高效插入、删除和查找最小元素的操作。它由计算机科学家Michael L. Fredman和Robert E. Tarjan在1984年提出，其...

    斐波那契堆的C#实现

    2. **FibonacciHeap** 类：作为整个堆的容器，维护最小节点的指针，以及用于合并堆的操作。 3. **Insert** 方法：向堆中插入一个新节点。新节点首先被单独作为一个小顶堆添加，然后与当前堆合并。 4. **ExtractMin...

    datastructure_斐波那契堆_二项堆_

    在这个主题中，我们将深入探讨两种重要的数据结构——斐波那契堆（Fibonacci Heap）和二项堆（Binary Heap）。它们在算法设计，特别是图论和最优化问题中扮演着至关重要的角色，比如Prim's最小生成树算法和Dijkstra'...

    斐波那契堆（fibheaps）讲解：背景和分析

    ### 斐波那契堆（Fibonacci Heaps）讲解：背景与分析 #### 一、动机与背景 斐波那契堆作为一种高效的数据结构，主要用于优化优先队列的性能。优先队列在计算机科学中有着广泛的应用，尤其是在解决网络优化问题时。...

    斐波那契堆.zip

    斐波那契堆是一种特殊的数据结构，主要用于优化某些算法，特别是在解决涉及图的最短路径问题时，能够显著提升计算效率。它是由Michael L. Fredman和Robert E. Tarjan在1987年提出的，结合了多个二项堆的优点，以实现...

    dijkstra算法的三种实现：数组，二叉堆，斐波那契堆 + 部分实验报告

    dijkstra算法的三种实现：数组，二叉堆，斐波那契堆 + 部分实验报告 dijkstra算法的三种实现：数组，二叉堆，斐波那契堆 + 部分实验报告 dijkstra算法的三种实现：数组，二叉堆，斐波那契堆 + 部分实验报告

    Fibonacci Heap and Dijktra

    斐波那契堆（Fibonacci Heap）是一种高级的数据结构，常用于图论算法中，如迪杰斯特拉算法（Dijkstra's Algorithm）来优化最短路径查找的效率。迪杰斯特拉算法本身是用于寻找带权有向图中源节点到其他所有节点的最短...

    Dijkstras:使用斐波那契堆实现Dijkstra算法

    斐波那契堆（Fibonacci Heap）是一种特殊的优先队列数据结构，它在处理大量元素和频繁插入、删除最小元素的操作时表现出高效的性能。在Dijkstra算法中，我们需要不断更新当前已知最短路径节点，并从这些节点出发探索...

    FibonacciHeap：Fibonacci堆实现

    Fibonacci堆是一种高效的数据结构，主要用于解决图的最小生成树、最短路径等问题，它在操作如插入、删除最小元素以及合并等操作上具有很好的时间复杂度。在这个名为"FibonacciHeap-master"的压缩包中，我们可以预期...

    0836-极智开发-解读斐波那契堆及示例代码

    0836_极智开发_解读斐波那契堆及示例代码

    二项堆和Fibonacci堆的分析与实现毕业论文.doc

    二项堆和Fibonacci堆的分析与实现毕业论文.doc

Magicbox
Global site tag (gtag.js) - Google Analytics