如何理解<Purely Functional Data Structures>中描述的分段二项式堆

Question

在纯功能数据结构论文的第6.3.1章中说:

然后,每当我们从一个新元素和一个排名为0 ... r-1的树段创建一个新树时,我们只需将新元素与该段中的第一个根(即,0级树的根)进行比较).较小的元素成为新的根,较大的元素成为根的0级子元素.

1. T0'是新树的等级0
2. T0..T(r-1)是从0到r-1的原始树
3. 较小的元素成为新的根,较大的元素成为根的0级子元素

问题是第3步导致两个等级1树,这与二项式堆冲突.

我误会了吗？

Answer 1

我们正在创建一棵等级为 r 的树。等级为 r 的树的结构是一个根节点，具有等级为 0..r-1 的 r 个子节点。

你引用的部分的意思是这样的。

1. 当我们得到一个新元素 x 时，我们将它与 T0 中的元素进行比较
2. 我们创建一个等级为 0 的新树 T0'，包含两个比较元素中较大的一个
3. 我们创建一个新节点 T，其中包含两个比较元素中较小的一个，并将 T0',T1,T2...T(r-1) 作为子节点

现在 T 是一个等级为 r 的二项树，并且是堆序的。