开发者

Regrading rank in Binomial queue

I am reading about Binomial queue operations here.

At bottom of link it is mentioned as

Implementation of a Binomial Queue

  1. deletemin operation requires ability to find all subtrees of the root. Thus children of each node should be available (say a linked list)
  2. deletemin requires that the children be ordered by the size of their subtrees.
  3. 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 siz开发者_开发技巧e 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.


As far as I understand, he tries to say: We store the rank, which is incidently the same as the no. of childen (that's how ranks for such trees are usually defined). Thus, you just store in each node the following:

  • data represents the element in the tree
  • first represents a pointer to the linked list of children (i.e. a pointer to the first child)
  • left is a pointer to the left neighbour
  • right is a pointer to the right neighbour
  • rank is simply the rank of the binomial tree


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜