CODEWITHSUNDEEP
haskelldata-structuresfunctional-programminglispml
wenlong
wenlong

Reputation: 1434

How to understand segmented binomial heaps described in <Purely Functional Data Structures>

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?

Upvotes: 8

Views: 839

Answers (1)

opqdonut
opqdonut

Reputation: 5159

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.

Upvotes: 4

Related Questions