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
- 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 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 treefirst
represents a pointer to the linked list of children (i.e. a pointer to the first child)left
is a pointer to the left neighbourright
is a pointer to the right neighbourrank
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.
精彩评论