2

I don't understand why Fibonacci heaps have marked nodes (picture). A node is marked when its child is deleted. Quoting from Wikipedia: "[Keeping degree of each node low] is achieved by the rule that we can cut at most one child of each non-root node. When a second child is cut, the node itself needs to be cut from its parent and becomes the root of a new tree."

Why do we need to do that? Why not just leave the node where it is after the second child is cut? The heap structure is not violated. I don't see the point of this optimization.

1 Answer 1

4

The reason is not that it would violate the heap invariant, but that it would lead to a state in which the heap would be inefficient.

The heap is efficient because after compaction there is only log(N) trees. To guarantee that you need to know that a tree with root degree k contains at least O(2k) nodes. But if you can cut nodes freely, you could cut all the second-level children and the tree would remain of degree k, but could get down to k+1 nodes.

This is prevented by tearing the tree apart and compacting it's parts again in next compaction step.

1
  • That's exactly what I was looking for! Makes perfect sense, thank you! Feb 18, 2013 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.