重新排序二项式队列中的排名
我正在此处阅读有关二项式队列操作的内容。
在链接的底部提到，
二项式队列
- 删除操作的实现需要能够找到根的所有子树。因此，每个节点的子节点应该可用（例如链表），
- deletemin 要求子节点按其子树的大小排序。
- 我们需要确保很容易合并头发。两棵二项树只有在大小相同时才能合并，因此树的大小必须存储在根中。合并时，一棵树成为另一棵树的最后一个子节点，因此我们应该跟踪每个节点的最后一个子节点。一个好的数据结构是循环双精度 链表每个节点的形式如下：
data | first |left | right |rank No. of |
--------------------------------------------
child |sibling |sibling| children
在上面作者的意思是“排名号？”，任何人都可以用例子解释一下。
I am reading about Binomial queue operations here.
At bottom of link it is mentioned as
Implementation of a Binomial Queue
- deletemin operation requires ability to find all subtrees of the root. Thus children of each node should be available (say a linked list)
- deletemin requires that the children be ordered by the size of their subtrees.
- we need to make sure it is easy to merge tress. Two binomial trees can be merged only if they have the same size, hence the size of the tree must be stored in the root. While merging, one of the trees becomes the last child of the other, so we should keep track of the last child of each node. A good data structure to use is a circular doubly
linked list what each node is of the following form:
data | first |left | right |rank No. of |
--------------------------------------------
child |sibling |sibling| children
In above what does author mean "rank No. Of? can any one please explain with example.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
据我了解，他试图说：我们存储
rank，顺便说一句，它与no相同。 childen（这就是通常定义此类树的排名的方式）。因此，您只需在每个节点中存储以下内容：data表示树中的元素first表示指向子项链表的指针（即指向第一个子项的指针） )left是指向左邻居的指针right是指向右邻居的指针rank只是二项式树的排名As far as I understand, he tries to say: We store the
rank, which is incidently the same as theno. of childen(that's how ranks for such trees are usually defined). Thus, you just store in each node the following:datarepresents the element in the treefirstrepresents a pointer to the linked list of children (i.e. a pointer to the first child)leftis a pointer to the left neighbourrightis a pointer to the right neighbourrankis simply the rank of the binomial tree请注意“两个二项式树只有具有相同大小才能合并，因此树的大小必须存储在根中”的要求。
看来作者没有放置“子树大小”字段，而是放置了“子树数量”字段。这很令人困惑，但对于实现来说这很好，因为子树的大小是 2^{# of Children}。因此，您可以比较子树的数量，而不是比较子树的大小。
Note the requirement "Two binomial trees can be merged only if they have the same size, hence the size of the tree must be stored in the root."
It seems that instead of a "size of subtree" field, the author put a "number of children" field. This is confusing, but for an implementation it is fine, because the size of the subtree is 2^{# of children}. So you can compare # of children instead of comparing size of subtree.