-
March 31st, 2009, 02:47 PM
#1
Fibonacci Heaps
I'm trying to implement a fibonacci heap, and I'm running into some troubles when trying to implement delete_node.
When implementing delete_min, I was assured that the size of the array necessary for the merge section was ceil(lg(n)), or, as I ended up implementing it for efficiency's sake, lg(n) + 1 (lg() is log-base-2(), of course). I was also told that the degree of a node is equal to the number of its children (and this is where it breaks down).
Imagine a fibonacci heap composed solely of a binomial heap of degree 2 (trivially achievable by adding 5 values and deleting the min once). Then delete the only node at depth 2, resulting in a node with 2 leaf nodes (with one of them being marked).
At this point:
n = 3
lg(n) + 1 = 2
degree(min) = 2
2 is outside the bounds of an array created with 2 elements. So, naturally, I could just change lg(n) + 1 to lg(n) + 2, but that doesn't seem right. I feel like I've misunderstood something.
Thanks.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|