算法导论期末复习（二项堆）

本文主要是介绍算法导论期末复习（二项堆），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

@算法导论

算法导论期末复习（二项堆）

1、二项树

定义：

二项树是一种递归定义的有序树，它只包含一个子节点，二叉树 $B_n$ 的是由两棵
$B_{n-1}$ 树构成的。其中一棵树的根是另一棵树根的左子树。

性质：

对于二项树 $B_k$ 有以下的性质：
①：共有2^k个节点。
②：树的高度为k。
③：在深度 i 处。恰好有 $C_k^i$ 个节点。
④：根的度数为 k，他大于任何其他节点的度数，并且根的子女，从左到右编号为
k-1，k-2，…，0，子女 i 是子树 $B_i$ 的根。

推论：

一棵包含n个节点的二项树中，任意节点的最大度数为 $l g n$ 。//性质①④可直接推的。

2、二项堆

定义：

二项堆是由满足以下性质的二项树组成的：
①：满足最小堆有序，二项堆中的每一个节点的关键字都大于或者等于其父节点的关键字。
②：对于非负整数 k ，堆中最多只有一棵二项树的根节点度数为 k 。

如下图所示为一个二项堆的实例：

二项堆表示：

每个节点包含了指向其父节点的指针p[x]，包含了指向其最左边孩子节点的指针child[x]，包含了指向其右兄弟节点的指针sibling[x] ，并且每个节点都有包含其子女个数的域degree[x]。对于堆中的每个二项树的根节点，组成了一个链表，称为根表，且按照各根的度数递增的方式排序。

如下图为二项堆的具体表示实例：
二项堆表示实例

3、二项堆的操作

寻找最小关键字：

由上面的二项堆定义可知，堆中的最小关键字一定在二项树的根节点中，所以直接遍历二项堆的根表，便可以得到二项堆的最小值，故时间复杂度应该为 $l g n$ 。

合并两个二项堆：

对于合并两个二项堆，就是不断合并两个二项堆中，度数相同的子树的并且将根节点插入到根表的过程。
我们首先确定合并两个 $B_{k-1}$ 成为 $B_k$ 树的伪代码实现过程(Y为子)：
1 BINOMIAL-LINK(Y,Z)
2 P[Y] = Z
3 SIBLING[Y] = CHILD[Z]
4 CHILD[Z] =Y
5 DEGREE[Z] = DEGREE[Z] +1

再来分析整个合并二项堆的伪代码，其中BINOMIAL-HEAP-MERGE函数是将二项堆 H1 和二项堆 H2 的根表合并成按度数单调递增的链表，具体伪代码如下图（合并过程有四种情况）：

在上图中的第16行的if 是和第18行的else配对的。代码中所提到的四种情形如下图所示：

在这里插入图片描述
代码中的四种情形，应该从第三种和第四种开始分析，较为容易理解。

插入一个结点

对于二项堆的插入过程，应该是先建立一个只含有一个该节点的二项堆H‘，再使用合并操作，将H和H’合并，即可将节点插入。

抽取具有最小关键字的结点

当我们从堆中抽取删除了最小关键字结点 x 后，如果 x 为一棵 $B_k$ 树的根，那么 x 的各子女从左往右分别为Bk-1，Bk-2，…，B0。我们要做的是将这些 X 的子女结点，逆转形成一个包含 k-1 个根节点的堆H’，再将 H 和 H’ 一起合并新堆。此时我们可以得到时间复杂度应为 $l g n$