二项式堆 嚷单罪围 degree Right sibling I Left-child 节点数据 清华大学末域恒 关于右兄弟的法则等 Operations on binomial heap 如果一个节点是其父节点的最右边的孩 1. Creating a new empty binomial heap 子,则该节点没有右兄弟,否则其右兄 弟为其父节点的比自己靠右的下一个孩 2. Minimum ·如果是根节点,其父节点为 ·孩子节点指向其最左孩子,否则为空 L. Ifkey(xmin then minekeyIxh yex 清华大学末斌恒 请华大学宋恒 Uniting two binomial heaps 合并步骤 两个相同阶数的二项式树的联结 第一步:融合,按照树的大小从小到大 Binomial-link(y, z) 排列两个堆的所有二项式树 1. Parently]ez ·第二步:从小到大联结相同的二项式 2. Siblingly]child[z] 树:如果当前大小相同的树连续只有 3. Child[z]ey 个跳过,只有两个联结,只有三个则联 4. Degree[z]degree[ z+ 结后两个,然后继续 清华大学末域恒 请华大学宋3 清华大学 宋斌恒 13 Head[H] Key value degree parent Right sibling Left-child 节点数据 结构 清华大学 宋斌恒 14 清华大学 宋斌恒 15 关于右兄弟的法则等 • 如果一个节点是其父节点的最右边的孩 子，则该节点没有右兄弟，否则其右兄 弟为其父节点的比自己靠右的下一个孩 子。 • 如果是根节点，其父节点为空。 • 孩子节点指向其最左孩子，否则为空 清华大学 宋斌恒 16 Operations on binomial heap • 1. Creating a new empty binomial heap: head[H]Ånull • 2. H.minimum 1. yÅnull 2. xÅhead[h] 3. minÅinfinity 4. While x != null 1. If key[x]<min then minÅkey[x], yÅx 2. xÅsibling[x] 5. return y 清华大学 宋斌恒 17 Uniting two binomial heaps • 两个相同阶数的二项式树的联结 • Binomial-link(y,z) 1. Parent[y]Åz 2. Sibling[y]Åchild[z] 3. Child[z]Åy 4. Degree[z]=degree[z]+1 清华大学 宋斌恒 18 合并步骤 • 第一步：融合，按照树的大小从小到大 排列两个堆的所有二项式树 • 第二步：从小到大联结相同的二项式 树：如果当前大小相同的树连续只有一 个跳过，只有两个联结，只有三个则联 结后两个，然后继续