联创 Lab 组新人任务第一弹。
关于斐波那契堆
结构与特点
- 斐波那契堆是由一组最小堆有序树构成的。每个节点的度数为其子节点的数目。树的度数为其根节点的度数。
- 斐波那契堆中的树都是有根的但是无序。每个节点x包含指向父节点的指针p[x]和指向任意一个子结点的child[x]。x的所有子节点都用双向循环链表链接起来，叫做x的子链表。子链表中的每一个节点y都有指向它的左兄弟的left[y]和右兄弟的right[y]。如果节点y是x仅有的子节点，则left[y]=right[y]=y。
- 斐波那契堆中所有树的根节点也用一个双向循环链表链接起来。
- 使用一个指针指向斐波那契堆中最小元素。 斐波那契堆将操作尽可能地延后，它的插入是懒惰的，只有在不得不进行合并操作时才进行合并。在极端情况下，它甚至是一个长度很大的链表。
插入操作
将一个节点直接插入到根链表中，并比较键值的大小，如果新节点的键值小于原有节点的键值，就将斐波那契堆的指向最小节点的指针指向它。
删除最小节点操作
- 先将最小节点的儿子插入到根链表中，再删除掉这个目标节点。再遍历根链表，合并所有根节点是相同度数的堆。
- 由于本次实现不需要实现对节点键值的改变或者根据键值删除节点，因此这里的斐波那契堆可以进行一定程度的简化：不再需要指向父亲节点的指针，也不需要第一个儿子是否被删除的标记。由于不需要维护指向父亲的指针，在将儿子们合并到根链表时的操作也可以简化，直接将两个链表合并即可。
实现斐波那契堆
代码文件
https://github.com/vaaandark/MyPriorityQueue
文件结构
- generator文件夹内有文件generator.c，用于生成测试数据。
- STLPriorityQueue文件夹内有文件stl_priority_queue.cpp，用STL中的Priority Queue编写，用于对照实验。
- src中为基于Fibonacci Heap的Priority Queue的具体实现。
- 脚本test.sh用于自动化测试，可以使用可选参数clean，用于清理之前测试出现的非代码文件。
- src_cpp为Set的C++实现。