8

In chapter 6.3.1 of the thesis Purely Functional Data Structures, says:

Then, whenever we create a new tree from a new element and a segment of trees of ranks 0... r-1, we simply compare the new element with the first root in the segment (i.e.,the root of the rank 0 tree). The smaller element becomes the new root and the larger element becomes the rank 0 child of the root.

  1. T0' is the new tree has rank 0
  2. T0..T(r-1) are the original trees rank 0 to r-1
  3. The smaller element becomes the new root and the larger element becomes rank 0 child of the root

The question is that step 3 result in two rank 1 trees, which is conflict with the binomial heaps.

Am I misunderstanding?

Improve this question

1 Answer 1

Reset to default
4

We are creating a tree of rank r. The structure of a tree of rank r is a root node with r children of ranks 0..r-1.

What the part you quoted means is this.

  1. When we get a new element x we compare it to the element in T0
  2. We create a new tree T0' of rank 0 containing the greater of the two compared elements
  3. We create a new node T containing the lesser of the two compared elements and with T0',T1,T2...T(r-1) as children

Now T is a binomial tree of rank r and it is in heap order.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

The heap contains r trees before and 1 tree after?
@wenlong: yes, r trees in the heap have been replaces with 1 tree. There might be other trees with ranks greater than r, though. They arent affected by this operation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.