haskell - 如何理解《纯函数式数据结构》中的分段二叉堆

Question

论文6.3.1章Purely Functional Data Structures , 说:

Then, whenever we create a new tree from a new element and a segment of trees of ranks 0... r-1, we simply compare the new element with the first root in the segment (i.e.,the root of the rank 0 tree). The smaller element becomes the new root and the larger element becomes the rank 0 child of the root.

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

问题是第 3 步产生了两棵 1 阶树，这与二项堆冲突。

我是不是误会了？

Answer 1

我们正在创建等级为 r 的树。秩为 r 的树的结构是根节点和秩为 0..r-1 的 r 个子节点。

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

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

现在 T 是一棵秩为 r 的二叉树，并且是堆序的。