- 浏览: 508785 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
jkxydp:
算法运行的结果根本就不对。
BM算法. -
soarwindzhang:
感谢博主的分享,我今天看了您的UFSET非递归的路径压缩时感觉 ...
并查集 -
zhangning290:
楼主好像只考虑了坏字符规则,。没有考虑好后缀
BM算法. -
lsm0622:
文字描述有错误 误导新学者
求有向图的强连通分量(scc):Tarjan算法 -
knightchen:
博主,你太强了!这篇文章对我学习C++多线程很有帮助!谢谢
并发学习之一_windows下ZThread在CodeBlocks上的安装与配置
学习的地方:
http://en.wikipedia.org/wiki/Talk:Fibonacci_heap
http://jicheng.ycool.com/post.2380567.html
1,先贴个代码:
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; } */
发表评论
-
为什么堆排比快排慢
2010-12-16 15:25 3019[节选]http://mindhacks.cn/200 ... -
使用map和hash_map的效率问题
2010-12-09 19:49 68911,选择map容器,是为了更快的从关键字查找到相关的对象。 与 ... -
斐波那契堆
2010-07-04 11:37 181, http://kmplayer.iteye.com/ad ... -
Sunday算法
2010-07-02 11:38 89831,Sunday算法是Daniel M.Sunday于1990 ... -
BM算法.
2010-07-02 10:53 77061,BM算法是Boyer-Moore算法的简称,由Boyer ... -
优先级队列
2010-06-17 23:15 11941,优先级队列是不同于 ... -
计数排序
2010-05-04 16:59 7831,计数排序是一个非基于比较的线性时间排序算法。 它对输入的数 ... -
归并排序
2010-05-04 16:47 9021,归并排序是建立在归并操作上的一种有效的排序算法。该算法是采 ... -
求大数阶层
2010-05-04 16:40 13421,思想类似于大数的加减乘法. 数组的每个元素维护一个4位数. ... -
基数排序
2010-05-03 16:45 889详细解释参考:http://en.wikipedia.org/ ... -
求两个数组的中位数
2010-05-02 12:08 41061,题目 有两个数组,均已经按升序排列好,编程序计算这两个数组 ... -
imba的bit向量
2010-04-22 17:30 9321,先给出一个模板. #include <iostr ... -
编写自己的malloc
2010-04-19 17:03 15101,如果一个程序大量调用malloc,程序的很多时间将会消耗在 ... -
快速排序
2010-04-01 13:50 7371,给出一个实现实例. #include <iost ... -
md5算法
2010-03-31 10:35 2666Message Digest Algorithm MD5( ... -
堆排序
2010-03-23 10:48 8911,"堆"定义 n个关 ... -
改进的线性筛法_寻找素数
2010-03-03 10:41 16121,实例代码: #include <iostream ... -
求有向图的强连通分量(scc):Tarjan算法
2010-02-28 15:41 143071,在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强 ... -
最近公共祖先LCA:Tarjan算法
2010-02-28 15:25 178401,并查集+dfs 对整个树进行深度优先遍历,并在遍历的过程中 ... -
寻找凸包的graham 扫描法
2010-02-27 21:39 70991,点集Q的凸包(convex hull)是指一个最小凸多边形 ...
相关推荐
二叉堆、二项堆和斐波那契堆是数据结构中的重要概念,它们都是堆数据结构的不同变体,主要用于高效地实现某些特定操作,如查找最大或最小元素、优先队列以及各种排序算法。在C++编程语言中,理解和实现这些堆结构...
2. 删除最小元素:斐波那契堆通过“瀑布修剪”(Fibonacci Heap Deletion)策略来优化这个操作。当删除最小元素时,会将所有与其相邻的子节点提升到其位置,这个过程可能引发树的重构,但总体上保证了操作的时间...
斐波那契堆是一种高效的优先队列数据结构,主要用于图的最小生成树算法,如Prim算法和Kruskal算法,以及Dijkstra最短路径算法。它由计算机科学家Frederick S.~Tarjan提出,其设计灵感来源于自然界中的斐波那契数列。...
斐波那契堆的python实现(优先队列),实现内容:merge(H), insert(v), find_min() # extractMin(), coalesce_step(), updateMin() # decreaseKey(v,k), delete(v)
斐波那契堆是一种高效的优先队列数据结构,主要用于图论中的最短路径算法,如Dijkstra算法和Prim算法。它的设计灵感来源于自然界中的斐波那契数列,通过巧妙地组织节点,使得插入、删除最小元素以及合并操作的时间...
斐波那契堆是一种高效的优先队列数据结构,它在计算机科学中,特别是在算法和图论领域具有重要的应用。在《算法导论》一书中,斐波那契堆被广泛讨论,因为它在解决诸如最短路径、最小生成树等算法问题时能提供高效的...
斐波那契堆(Fibonacci Heap)是一种高级的数据结构,常用于图的最短路径算法,如Dijkstra算法和Floyd-Warshall算法,以及优先队列等场景。它是基于树的堆结构,由多个堆节点组成,每个节点包含一个键值、一个指向其...
从提供的文件"www.pudn.com.txt"和"FibonacciHeap"来看,可能包含了关于斐波那契堆的C++代码实现。具体实现细节可能包括类定义、成员函数(如insert、delete_min、decrease_key等)以及相应的辅助函数。 总的来说...
斐波那契堆(Fibonacci Heap)是一种高级的数据结构,主要用于解决图的最短路径问题、优先队列等需要高效插入、删除和查找最小元素的操作。它由计算机科学家Michael L. Fredman和Robert E. Tarjan在1984年提出,其...
2. **FibonacciHeap** 类:作为整个堆的容器,维护最小节点的指针,以及用于合并堆的操作。 3. **Insert** 方法:向堆中插入一个新节点。新节点首先被单独作为一个小顶堆添加,然后与当前堆合并。 4. **ExtractMin...
在这个主题中,我们将深入探讨两种重要的数据结构——斐波那契堆(Fibonacci Heap)和二项堆(Binary Heap)。它们在算法设计,特别是图论和最优化问题中扮演着至关重要的角色,比如Prim's最小生成树算法和Dijkstra'...
### 斐波那契堆(Fibonacci Heaps)讲解:背景与分析 #### 一、动机与背景 斐波那契堆作为一种高效的数据结构,主要用于优化优先队列的性能。优先队列在计算机科学中有着广泛的应用,尤其是在解决网络优化问题时。...
斐波那契堆是一种特殊的数据结构,主要用于优化某些算法,特别是在解决涉及图的最短路径问题时,能够显著提升计算效率。它是由Michael L. Fredman和Robert E. Tarjan在1987年提出的,结合了多个二项堆的优点,以实现...
dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告
斐波那契堆(Fibonacci Heap)是一种高级的数据结构,常用于图论算法中,如迪杰斯特拉算法(Dijkstra's Algorithm)来优化最短路径查找的效率。迪杰斯特拉算法本身是用于寻找带权有向图中源节点到其他所有节点的最短...
斐波那契堆(Fibonacci Heap)是一种特殊的优先队列数据结构,它在处理大量元素和频繁插入、删除最小元素的操作时表现出高效的性能。在Dijkstra算法中,我们需要不断更新当前已知最短路径节点,并从这些节点出发探索...
Fibonacci堆是一种高效的数据结构,主要用于解决图的最小生成树、最短路径等问题,它在操作如插入、删除最小元素以及合并等操作上具有很好的时间复杂度。在这个名为"FibonacciHeap-master"的压缩包中,我们可以预期...
0836_极智开发_解读斐波那契堆及示例代码
二项堆和Fibonacci堆的分析与实现毕业论文.doc