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.