How to split binomial heap in O(log(n))?
- From: Billy <stasgold@xxxxxxxxx>
- Date: 26 Apr 2007 12:58:42 -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 within O(log(n))
complexity .
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 in advance,
.
- Prev by Date: Re: Find the type
- Next by Date: Fibonacci heap and Dijkstra's algorithm
- Previous by thread: Find the type
- Next by thread: Fibonacci heap and Dijkstra's algorithm
- Index(es):