算法导论 斐波那契堆

1. 定义

   1. 堆H
      1. 最小结点min：指向最小关键字key的根结点
      2. n表示当前堆中结点的个数
   2. 结点x
      1. 最小堆性质：每个结点的关键字key均大于等于父结点的关键字
      2. 根链表：所有的根结点都通过left,right指针形成一个环形链表
      3. 父类指针为p,左右兄弟结点为left,right,指向任何一个子结点指针为child,孩子的数目为degree,mark是否失去过孩子

2. 操作

   1. 插入结点：直接在根链表最后插入结点
   2. 抽取最小结点：将最小结点的子结点最入到根链表中，然后删除最小结点，并合并链表
   3. 合并根链表：用一个数组保存各个根链表结点的度数，度数相同则合并
   4. 结点关键值减值：直接将关键字修改，如果小于父类，则将该关键字放在根链表中，并将父类mark改为true,两次mark则要将父类结点放到根链表中
   5. 删除：先将结点关键字改为最小值，然后调用抽取最小结点方法

3. 源代码

   1. https://gitee.com/beimuaihui/LayaAir/blob/my_introduction_to_algorithms/src/samples/algorith/C19FibHeap.ts
   2. 堆合并union时是放在根结点链表最后，consolidate合并根链表时，是作为新的子结点child放在最前面

4. 运行结果

   1. 

5. 参考

   1. https://www.cnblogs.com/skywang12345/p/3659060.html