二项堆和fibonacci堆的分析与实现_毕业设计论文(编辑修改稿)

二项堆和fibonacci堆的分析与实现_毕业设计论文(编辑修改稿)内容摘要：

二项堆是指满足以下性质的二项树的集合： (1)每棵二项树都满足堆性质，即任意结点关键字大于等于其父结点的关键字。 (2)集合中 不能有两棵或者两棵以上的二项树有相同度数。 上图是 含 13 个结点的二项堆 示意图。 由于 我们并不 需要对二项树的根结点 9 进行 随机存取 的操作 ， 我们将这些根节点按照度数从小到大的次序链接成一条单链 ，形成的链表我们称为主链。 因此 以上第一个性质保证了二项树的 主链 包含了最小的关键字。 以上第二个性质则说明结点数为 n 的二项堆 的根链上至多 有棵二项树。 对于二叉堆中的每个节点 x 包括以 下属性：子女个数，最左孩子 ，右兄弟 ，父节点 ， 关键字。 对于一个抽象的二项堆 H， 表示主链首部， 表示堆中节点的个数。 二项堆的操作 合并 上图是两棵二项树合并的示意图。 上图是两个二叉堆合并的示意图。 最基本的为二个度数相同的二项树的合并。 由于二项树根结点包含最小的关键字，因此在二颗树合并时，只需比较二个根结点关键字的大小，其中含小关键字的结点成为结果树的根结点，另一棵树则变成结果树的 最左孩子。 伪代码如下： Bin_Link(y, z) 1 ← z 2 ← 3 ← y 4 ← +1 福州大学本科生毕业设计 (论文 ) 10 上图是如何遍历主链的示意图。 两个二项堆的合并可按如下步骤进行： 因为主链上的根节点的 度数 i 从小到大排列且不存在两个相同度数的根节点在同一主链上，因此可以对两个主链按照根节点的度数从小到大进行遍历合并得到一条主链。 在得到的这条主链上度数为i 的根节点至多有两个且相邻。 因此我们对主链进行一次遍历，在遍历过程中 度数为 i的根节点只可能有 1 个， 2 个或者 3 个。 我们利用三个指针 prev_x， x， next_x来遍历主链。 来如果当前度数为 i的根结只有一个或者三个则指针指向下一个节点，如果只有两个则合并两棵二叉树并且将新的根节点加入主链。 由于含有 n个节点的二叉堆的主链长度不超过 logn+1，并且我们只遍历了两遍主链，因此合并 操作的时间复杂度为。 伪代码如下 : Bin_Union(H) 1 H = Bin_Make() 2 = Bin_Merge(H1,H2) 3 free objects H1 and H2 but not the lists they point to 4 if == NIL 5 return H 6 prev_x = NIL 7 x = 8 next_x = 9 while next_x != NIL 10 if ( != ) or ( != NIL and == ) 11 prev_x = x, x = next 12 else if = 13 = 14 Bin_Link(next_x, x) 15 else if prev_x == NIL 16 = next_x 17 else 18 = next_x 19 Bin_Link(x, next_x) 20 x = next_x 21 next_x = 11 22 return H 插入 创建一个只包含要插入关键字的堆，再将此堆与原先的二项堆进行合并，即可得到插入后的堆。 由于需要合并 操作的时间复杂度为 ， 因此 插入操作 的时间复杂度为。 伪代码如下： Bin_Insert(H， x) 1 subH = Bin_Make() 2 = = = = = NIL 3 H = Bin_Union(H, subH) 查找最小关键字 由于满足最小堆性质，只需 对二项堆的主链进行一遍遍历 即可， 因为 n 个节点的二项堆的主链长度不超过 logn+1，所以查找 最小关键字操作的时间复杂度为。 伪代码如下： Bin_Top (H) 1 y = NIL 2 x = 3 min = infinite 4 while x != NIL 5 if min 6 min = 7 y = x 8 x = 9 return y 删除最小关键字 首先 先找到最小关键字所在结点，将 该节点的 子树看作一个独立的二项堆，再将此堆合并到原先的堆中 ，然后删除最小关键节点 即可。 由于每棵树最多有logn+1 棵子树，创建新堆的时间为。 同时合并堆的时间也为 ，故整个操作 的时间复杂度 为。 伪代码如下： Bin_Pop(H) 1 find the node with smallest key value on main chain and remove it from main chain. 2 subH = Bin_Make() 3 reverse the order of the linked list of x’s children, set the p field of each child to NIL and set head[H] to the the head of the resulting list. 4 H = Bin_Union(H, subH) 5 return x 福州大学本科生毕业设计 (论文 ) 12 减小关键字的值 由于 在减小关键字的值后，可能不 再 满足最小堆性质。 此时，将其所在结点与父结点交换关键字 同时将指针指向父节点。 重复上述操作直到该节点为根节点或者该节点的关键值小于其父节点的关键字及 最小堆性质得到满足。 操作 的时间复杂度 为。 伪代码如下： Bin_Decrease(H， x, k) 1 = k ,y = x, z = 2 while z !=NIL and 3 swamp and 4 y = z, z = 删除 将需要删除的结点的关键字的值减小到负无穷大（比二项堆中的其他所有关键字的值都小即可），再删除最小关键字的结点即可。 伪代码如下： Bin_Delete(H, x) 1 Bin_Decrease(H, x, infinite) 2 Bin_Pop(H) 13 第 4 章 斐波那契堆 斐波纳契堆定义 斐波那契堆是计 算计科学中 中最小堆有 序树 的集合 ， 它和 二项堆 有类似的性质。 斐波那契堆 不涉及删除元素的操作有 O(1)的平摊时间 ，因此如果程序中Decrease 和 Delete 操作较少则能够获得极高 效率。 斐波那契堆中 每个节点 x 包含指向父节点的指针 ， 指向任意一个子结点的 ，表示 x 的节点个数， 指向它的左兄弟的 和右兄弟的。 同时 x 的所有子节点都用双向循环链表链接起来。 斐波纳契堆的 特点 与二项堆相似 ,斐波那契堆 也是一种可合并堆 ，是 由一组 堆有序 树 Decrease 和构 成的集合。 如果不对斐波纳契堆进行 Decrease 和 Delete 操作那么集合中的树都是二叉树。 可是如果存在 Decrease 和 Delete 操作时必然会破坏二项图的结构。 在这种情况下会出现 树高为 k，结点个数少于 2k 的情况。 与二项堆不同的是主链上的堆有序树不必按照度数大小从小到大排列。 上图是斐波那契堆的示意图。 斐波那契堆中每个节点的属性包括： 父节点 ， 指向任一子女的指针， 左兄弟 ， 右兄弟 ， 子女的个数 ， 布尔值域。 其中任意节点的所有子女被组织成循环双向链表， 表示节点 x 成为另一个节点的 子节点以来是否失去了一个孩子。 对于一个 特 定的斐波那契堆 ，我们构造一个数据结构 H， 其中 表示堆的大小， 指向堆中最小节点。 在斐波福州大学本科生毕业设计 (论文 ) 14 那契堆中，所有树的根 节点 都链接成一个环形的双链表，称为堆的 根表。 斐波纳契堆操作 斐波那契堆支持所有的堆操作，对于不涉及 Delete 的操作有 O(1)的均摊运行时间，其关键思想是将主链上的根节点的合并操作尽可能退后，来达到提高时间效率的目的。 创建一个新的斐波那契堆 过程 Fib_Make() 分配并 初始化一个 斐波那契堆对象 H。 插入一个结点 首先分配并且初始化一个节点 x 然后 加入 H 的根表中。 伪代码 如下 ： Fib_Insert(H, x) 1 = 0, = NIL, = NIL, = x, = x, ← =FALSE 2 merge the root list which contains x to root list H 3 if = =NIL or 4 = x 5 = + 1 下 图将关键字为 21 的结点插入斐波那契堆 的示意图。 合并两个斐波那契堆 由于双向链表的数据结构同时根表上的节点度数无序的性质，因此只需把两个根表连接同时比较最小关键节点取其中较小的即可。 伪代码 如下 ： Fib_Union(H1, H2) 1 H = Fib_Make() 2 = 3 merge the root list of H2 with the root list of H 4 if (。