[CST-2] Binomial Heaps

[Chris Applegate]

Anyone know whether the cost of creating a Binomial Heap from an
unsorted set of arbitrary data size n can be reduced from O(n log n)
like that for a normal heap can?

It can obviously be O(n log n) - for each element, create a one-element
binary heap, merge in with the existing heap, each merge costs O(log n),
do for n digits.

But I think I can get it down to O(n) - adding in a new heap is
effectively the same cost as adding 1 to a binary number (and has O(1)
cost), as ACN says. Half of this time (when the number is even), the
operation will involve no carries whatsoever and thus takes one bit
addition. A quarter of the time we'll have one carry to perform (e.g.
001+001 or 101+001) and thus two additions, an eighth of the time three
additions (e.g. 011 + 001) and so on...

So in actual fact, by adding one to an empty heap n-times we are
performing on average:

[SUM(1 to log n) n/2^n] bit additions per element.

Sum this to infinity and you get 2 (I think). So no more than 2 bit
additions are required per new element added, if we build our adder
right...

Which means we can add all our elements in O(n) time.

Wrong, right? I think this is roughly related to the proof that normal
heaps can be done in O(n) time as said in the Cormen & Rivest book, but
I'm now using the properties of the width of the top row rather than
tree height as the factor to make it go faster.

(If this was covered in the lecture and I was asleep at the time or
something then sorry...)

Cheerio,

Chris
do something lastminute.work

Chris Applegate
Room X6, Corpus Christi College, Cambridge, CB2 1RH
chris@qwghlm.co.uk / www.qwghlm.co.uk / [Redacted by SRCF sysadmins on request]
ICQ 41706821          PGP key available on request