斐波那契堆

✍ dations ◷ 2025-09-16 12:04:51 #数据结构,堆

斐波那契堆(Fibonacci heap)是计算机科学中树的集合。它比二项堆具有更好的平摊分析性能,可用于实现合并优先队列。不涉及删除元素的操作有O(1)的平摊时间。 Extract-Min和Delete的数目和其它相比,较小时效率更佳。稠密图每次decrease key只要O(1)的平摊时间,和二项堆的O(lg n)相比是巨大的改进。

斐波纳契堆于1984年由Michael L. Fredman与Robert E. Tarjan提出,1987年公开发表。名字来源于运行时分析使用的斐波那契数。

斐波那契堆是由一组最小堆有序树构成的。每个节点的度数为其子节点的数目。树的度数为其根节点的度数。

斐波那契堆中的树都是有根的但是无序。每个节点包含指向父节点的指针和指向任意一个子结点的。x的所有子节点都用双向循环链表链接起来,叫做的子链表。子链表中的每一个节点都有指向它的左兄弟的和右兄弟的。如果节点是仅有的子节点,则。

斐波那契堆中所有树的根节点也用一个双向循环链表链接起来。

使用一个指针指向斐波那契堆中最小元素。

此处示例中使用的编程语言为C

每个结点x的域

//斐波那契结点ADTstruct FibonacciHeapNode {    int key;       //结点    int degree;    //度    FibonacciHeapNode * left;  //左兄弟    FibonacciHeapNode * right; //右兄弟    FibonacciHeapNode * parent; //父结点    FibonacciHeapNode * child;  //第一个孩子结点    bool marked;           //是否被删除第1个孩子};typedef FibonacciHeapNode FibNode;

对于一个给定的斐波那契堆H,可以通过指向包含最小关键字的树根的指针min来访问,这个结点被称为斐波那契堆中的最小结点。如果一个斐波那契堆H是空的,则min = NIL. 在一个斐波那契堆中,所有树的根都通过left和right指针链接成一个环形的双向链表,称为堆的根表。于是,指针min就指向根表中具有最小关键字的结点。

//斐波那契堆ADTstruct FibonacciHeap {    int keyNum;   //堆中结点个数    FibonacciHeapNode * min;//最小堆,根结点    int maxNumOfDegree;   //最大度    FibonacciHeapNode * * cons;//指向最大度的内存区域};typedef FibonacciHeap FibHeap;

创建一个空的斐波那契堆,过程MAKE-FIB-HEAP 分配并返回一个斐波那契堆对象H;

//初始化一个空的Fibonacci HeapFibHeap * FibHeapMake() {    FibHeap * heap = NULL;    heap = (FibHeap *) malloc(sizeof(FibHeap));    if (NULL == heap) {        puts("Out of Space!!");        exit(1);    }    memset(heap, 0, sizeof(FibHeap));    return heap;} //初始化结点xFibNode * FibHeapNodeMake() {    FibNode * x = NULL;    x = (FibNode *) malloc(sizeof(FibNode));    if (NULL == x) {        puts("Out of Space!!");        exit(1);    }    memset(x, 0, sizeof(FibNode));    x->left = x->right = x;    return x;}

插入一个节点

创建一个仅包含一个节点的新的斐波纳契堆,然后执行堆合并。

由于用一个指针指向了具有最小值的根节点,因此查找最小的节点是简单的操作。

简单合并两个斐波纳契堆的根表。即把两个斐波纳契堆的所有树的根首尾衔接并置。

分为三步:

对一个节点的键值降低后,自键值降低的节点开始自下而上的迭代执行下述操作,直至到根节点或一个未被标记(marked)节点为止:

如果当前节点键值小于其父节点的键值,则把该节点及其子树摘下来作为堆的新树的根节点;其原父节点如果是被标记(marked)节点,则也被摘下来作为堆的新树的根节点;如果其原父节点不是被标记(marked)节点且不是根节点,则其原父节点被加标记。

如果堆的新树的根节点被标记(marked),则去除该标记。

把被删除节点的键值调整为负无穷小,然后执行“降低一个节点的键值”算法,然后再执行“删除最小节点”算法。

相关

  • 十字军国家十字军国家指经由十字军东征而建立之拉丁国家,他们建立国家时,一般都会将法兰克人那套成熟的采邑制度移植至新征服地,而他们所征服之地区,一般都会同时设立拉丁主教,这些国家之存
  • 水热合成法水热合成法是一种常用的无机材料的合成方法,在纳米材料、生物材料和地质材料中具有广泛的应用。水热/溶剂热合成法的主要步骤是将反应原料配置成溶液在水热釜中封装并加热至
  • 磷酸基磷酸(英语:phosphoric acid)或称为正磷酸(orthophosphoric acid),化学式H3PO4,是一种常见的无机酸,不易挥发,不易分解,几乎没有氧化性。具有酸的通性,是三元弱酸,其酸性比盐酸、硫酸、硝
  • 八音定诀《八音定诀》为清朝(1875年)叶开恩所编著的一部以厦门音主,混合著漳泉腔的闽南语音韵学书籍。
  • 林猪属大林猪(学名:Hylochoerus meinertzhageni),是偶蹄目猪科大林猪属中唯一的一种,分布于西非和中部非洲地区。其种加词“meinertzhageni”得名于英国军官及动物学家理查德·梅纳茨哈
  • 明尼阿波利斯艺术设计学院明尼阿波利斯艺术与设计学院 (Minneapolis College of Art and Design,缩写为MCAD)是一所私立,非盈利性质,四年制,包含学士后教育,专精于视觉艺术的大学。 该学院位于美国,明尼苏
  • 铁路支线铁路支线(branch line)是相对于铁路干线(main line),为较短的,一端与干线相接的铁路线。等级偏低,以单线铁路、普速铁路或非电气化铁路为主。工业专用线(industrial spur)用于铁路客
  • 爱德华·格里格爱德华·哈盖鲁普·格里格(挪威语:Edvard Hagerup Grieg,1843年6月15日-1907年9月4日),挪威作曲家,浪漫主义音乐时期的重要作曲家之一。爱德华·格里格出生于卑尔根,祖先是苏格兰人,
  • 倪蒋怀倪蒋怀(1894年8月12日-1943年4月21日),原名君怀,台湾台北瑞芳(今新北市瑞芳区)人。被认为是台湾第一位西画家,是水彩画家。绘画之余,兼营矿产事业,一生倾囊贡献于台湾美术之振兴及艺术
  • 安硕MSCI加拿大指数基金安硕MSCI加拿大指数基金(NYSE:EWC)是于纽约证券交易所上市的交易所交易基金,这个是在投资上市的MSCI加拿大成份股最有价值基础企业股份类别。现时基金持股比重最大公司(按所占比