在复杂性队列队列中调整排名

Question

我正在阅读有关生物统计排队操作here。

在链路的底部它被提及作为一个二项式队列

1. deletemin操作

   实现需要的能力来找到根的所有子树。因此，每个节点的子节点应该可用（比如链表）

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

 
data | first |left | right |rank No. of | 
-------------------------------------------- 
     child |sibling |sibling| children 

在上面是什么意思作家“排名号可以在任何一个请与例子解释一下吗？

Answer 1

据我所知，他试图说：我们存储了rank，这与no. of childen显然是相同的（这就是通常定义的树的排名），因此，您只需在每个节点中存储以下：

• data表示树中的元素
• first表示指向儿童链接列表的指针（即，一个指向第一个孩子）
• left是一个指向左边的邻居
• right是一个指针向右邻居
• rank是二叉树

Answer 2

注的要求仅仅排名“两个二叉树只有在它们具有相同的大小时才可以合并，因此树的大小必须存储在根中。”

看来，作为一个“大小的子树”字段，作者把一个“数字的孩子”字段。这很令人困惑，但是对于实现来说，这很好，因为子树的大小是2^{children`}。因此，您可以比较＃个孩子，而不是比较子树的大小。