一、二项树
1、定义
- 递归定义的有序树。二项树B0包含一个结点，二项树Bk 由两颗二项树B(k-1) 连接而成，其中一课的根是另一棵根的最左子树。
2、性质
二项树Bk:
- 共有2^k 个结点；
- 树的高度为k；
- 在深度为i 处有 C(k，i)个结点；
- 根的度数为k，它大于其他结点的度数；并且，如果根的子女从左到右编号为k-1，k-2，……，0，则子女i 是子树Bi 的根；
推论：
- 在一棵包含n 个结点的二项树中，任意结点的最大度数为 lg(n)。
二、二项堆
1、定义
二项堆H 由一组 满足以下条件 的二项树组成 ：
H中的每棵二项树都遵循最小堆性质，结点的关键字大于等于其父节点的关键字，这样的树是最小堆有序的。—-在一棵最小堆有序的二项树中，根包含了最小的关键字；
对任意非负整数k，在H中 至多有一棵二项树的根具有度数k。—-包含n个结点的二项堆H中，至多有lgn(向下取整)+1 棵二项树。
2、根表
- 每课二项树按 左孩子、右兄弟的方式存储；
- 一个二项堆中的各二项树的根被组织成一个单向链表，根的度数从小到大排列。
3、创建
Make-Binomil-Heap 时间：Θ(n)。
##4、操作
1）、寻找最小关键字
Binomil-Heap-Minimum ，二项堆最小堆有序，最小关键字在根结点，最多检查lgn(向下取整)+1 棵二项树，时间：O(lgn)。
2）、合并两个二项堆
Binomil-Heap-Union：
- Merge，将H1 和 H2 的根表合并成一个链表H，按度数单调递增排序；
- 将度数相等的根连接起来，直到每个度数至多有一个根时为止。
时间：O(lgn)。其中n 为H1 和H2 中结点总数。
3）、插入一个结点
Binomil-Heap-Insert 时间：O(lgn)。
4）、抽取具有最小关键字的结点
Binomil-Heap-Extract-Min 时间：O(lgn)。
5）、减小关键字的值
Binomil-Heap-Decrease-Key(H，x，k):
- 减值；
- 冒泡上升，直到满足最小堆有序。
时间：O(lgn)。
6）、删除一个关键字
Binomil-Heap-Delete(H，x):
- 给x赋值负无穷；
- 调用Binomil-Heap-Decrease-Key(H，x，k)使其冒泡上升到树根；
- 调用Binomil-Heap-Extract-Min 将根从H中去掉。
时间：O(lgn)。
三、斐波那契堆
1、定义
- 一系列具有最小堆序的有根树的集合。
2、根表
- 所有树的根，都用其left 和right 指针链成一个环形双向链表。
- 因为 H.min 指向根链表中关键字最小的结点，所以根链表中的树次序可以任意。
3、势函数
$ Φ(H) = t(H) + 2m(H) $
其中，t(H) 表示H 中根链表中树的数目，m(H) 表示H 中已标记的结点数目。
4、最大度数
一个具有n 个结点的斐波那契堆中，任意结点的度数的上界为$$O(lgn)$$
5、操作
1）、创建
时间：O(1)
2）插入一个结点
- 插入根表
- 若有必要，更新H.min
- H.n 加一
时间：O(1)
3）寻找最小结点
- 通过H.min
时间：O(1)
4）两个斐波那契堆合并
- 根链表链接成新的根链表；
- 设定H.min
- 设定H.n
时间：O(1)
5）抽取最小结点
- 将最小结点的每个孩子变成根结点；
- 从根链表中删除最小结点；
- 把具有相同度数的根结点合并，直到每个度数至多有一个根在根链表中。
摊还代价： $O(lgn)$
6 ）关键字减值
- 把新关键字赋值给x；
- 测试是否违反最小堆序；
- 若违反，做改变调整；
摊还代价： $O(1)$
7）删除一个结点
- 把负无穷赋值给x，使x成为最小结点；
- 调用Fib-Heap-Extract-Min删除x。
时间： $O(1)$