斐波那契堆

✍ dations ◷ 2025-07-03 13:45:17 #数据结构,堆

斐波那契堆(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),则去除该标记。

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

相关

  • J·J·汤姆孙约瑟夫·汤姆孙爵士,OM,FRS(英语:Sir Joseph John Thomson,1856年12月18日-1940年8月30日,简称J.J.Thomson),英国物理学家和诺贝尔物理学奖获得者, 他发现了电子并测定了其质荷比,这是
  • 月球运动论月球运动论的目的是计算月球的运动。月球有许多不规律(或是摄动)的运动,历史上科学家曾多次尝试去了解并计算它们,经历屡次失败下这一课题曾经是历史上的世纪难题,但月球运动已是
  • 锦绣中华深圳锦绣中华民俗村是一个以中国文化为本而设计的主题公园,位处中国广东省深圳市南山区华侨城,创建于1988年,由深圳锦绣中华发展有限公司营运。锦绣中华微缩景区占地30万平方米
  • 威廉斯塔德威廉斯塔德(荷兰语:Willemstad,或意译作威廉城)是荷兰王国在加勒比海的自治国库拉索(Curaçao) 的首府与该岛的主要都市,人口约为125,000人。在2010年荷属安的列斯解体之前,威廉市
  • 邦联陆军合计服役人数1,082,119联盟军(Confederate Army),即美国南北战争(美国内战 1861–1865)时期南方联盟方面陆军,亦称南军(Southern Army)。在美国南北战争期间,联盟军主要与北方联邦
  • 迈克尔·扬迈克尔·沃伦·扬(英语:Michael Warren Young,1949年3月28日-),美国遗传学家、美国国家科学院院士。1975年获得克萨斯大学奥斯汀分校博士学位,1978年起任洛克菲勒大学教员,后成为该
  • 中华秋沙鸭中华秋沙鸭(学名:)为鸭科秋沙鸭属的鸟类,也称鳞胁秋沙鸭、唐秋沙鸭。因英文名有称“Chinese merganser”,也经常被称为“国鸭”。分布于俄罗斯西伯利亚以及中国的黑龙江、吉林、
  • 费奥多尔·伊万诺维奇·托尔布欣费奥多尔·伊万诺维奇·托尔布欣(俄语:Фёдор Иванович Толбухин,1894年6月16日-1949年10月17日),苏联军事家,政治家,战时第七个晋升苏联元帅 。他是唯一一位死
  • 维多利亚广场维多利亚广场(Victoria Square)是英国伦敦的一个小型住宅广场,位于白金汉宫西南。该广场包括大约25座维多利亚时期五层住宅,均为二级保护建筑,由设计师马修·怀亚特爵士建于19世
  • 于家庄乡于家庄乡,是中华人民共和国河北省保定市满城区下辖的一个乡镇级行政单位。于家庄乡下辖以下地区:于家庄村、郭村、郎村、汤村、五里铺村、李铁庄村和庞村。