How to split binomial heap in O(log(n))?
- From: Billy <stasgold@xxxxxxxxx>
- Date: 26 Apr 2007 07:18:09 -0700
Hello.
The question is how to split binomial heap (size n) into binomial heap
of size k (k<n) and binomial heap of size n-k with given complexity
O(log(n)).
I've thought of something like traveling through binomial trees list
( from zero to higher orders) until sum of the trees' sizes exceeds
k , stepping back , breaking the next tree unto chunks and joining
the chunks with smaller trees until I'd get k elements.
But this seems too complicated and messy to implement and it would
surely take more then log(n) because of joining .
Is over there some simple algorithm that does the job in given
O(log(n)) complexity ?
Thanks i advance,
.
- Prev by Date: Re: Change for a Dollar
- Next by Date: Re: [C++] Command line parser
- Previous by thread: CfP: 7th Domain-Specific Modeling workshop at OOPSLA
- Next by thread: Take part in my research project
- Index(es):