algorithm - 二项式队列中的重新排序等级

Question

我在这里阅读有关二项式队列操作的信息。

在链接的底部，它被称为

二项式队列的实现

1. deletemin 操作需要能够找到根的所有子树。因此每个节点的子节点应该是可用的（比如一个链表）
2. deletemin 要求子节点按其子树的大小排序。
3. 我们需要确保很容易合并tress。只有大小相同的两棵二叉树才能合并，因此树的大小必须存储在根中。合并时，其中一棵树成为另一棵树的最后一个子节点，因此我们应该跟踪每个节点的最后一个子节点。一个好的数据结构是循环双向链表，每个节点的形式如下：

数据 | 第一个 |左 | 右 |排名第 |
------------------------------------------
       孩子 |兄弟姐妹 |兄弟姐妹| 孩子们

在上面作者的意思是“排名No. Of？”任何人都可以举例说明。

Answer 1

据我了解，他试图说：我们存储rank，顺便说一句，它与 相同no. of childen（这就是通常定义此类树的等级的方式）。因此，您只需在每个节点中存储以下内容：

• data表示树中的元素
• first表示一个指向子链表的指针（即指向第一个子链表的指针）
• left是指向左邻居的指针
• right是指向右邻居的指针
• rank只是二叉树的等级

Answer 2

请注意“只有两个二叉树的大小相同时才能合并，因此树的大小必须存储在根中”的要求。

似乎作者没有放置“子树的大小”字段，而是放置了“子树的数量”字段。这很令人困惑，但对于实现来说这很好，因为子树的大小是 2^{# of children}。所以你可以比较孩子的数量而不是比较子树的大小。