（二项树和二项堆）二项树Bk是一棵递归定义的有序树。如下图所示，二项树B0仅包含一个节点。二项树Bk是由两个二项树Bk-1组成，这两棵树按照一棵树的根是另一棵树根的最左孩子的方式连接。下图所示是B0到B4。
a.对于二项树Bk，证明：
- 一共有2k个节点
- 数的高度是k
- 对于i=0,1,2,...,k深度为i的节点恰有
个
- 根的度数为k，它比其他任何节点的度数都要大，此外如图所示，如果把根的孩子从左到右编号为k-1,k-2,...,0，那么孩子i时子树Bi的根。
- 每个节点具有一个关键字（与斐波拉契堆相同）
- H中的每个二项树遵循最小堆性质
- 对于任意的非负整数k，H中最多有一个二项树的根的度数为k
棵二项树组成。 假定按如下方式表述二项堆。用左孩子右邻兄弟方案表示二项堆中的每一棵二项树。每个节点包含一个关键字，指向它父节点的指针，指向它最左孩子的指针和指向它右邻兄弟的指针（这些指针一些情况下是NIL）。以及它的度数（如同斐波拉契堆，表示为有多少孩子）。这些根组成了一个单向链接的根链表，并以根的度数从小到大排列，可以通过一个指向根链表第一个节点的指针来访问二项堆。
c.完整描述如何表示一个二项堆（例如，对属性进行命名，描述属性值什么时候为NIL，定义根链表是怎么组织的），并说明如何用实现斐波拉契堆一样的方式来实现在二项堆上同样的7个操作。每一个操作的最坏时间应该为O(lgn)，其中n为二项堆中的节点数目（或对于UNION操作，为要被合并的两个二叉堆中的节点数）。MAKE-HEAP操作应为常数时间。
d.假定仅仅要实现在一个斐波拉契堆上的可合并堆操作（即并不实现DECREASE-KEY和DELETE操作）。斐波拉契堆中的树与二项堆中的树有何相似之处？有什么区别？证明在一个n个节点的斐波拉契堆中最大度数最多为
e.McGee教授提出了一个基于斐波拉契堆的新的数据结构。一个McGee堆具有与斐波拉契堆相同的结构，并且只支持可合并堆操作。除了插入和合并在最后一步中合并根链表外，其他操作的实现方式均与斐波拉契堆中的实现方式相同。McGee堆上各操作的最坏情况运行时间是多少？
