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.


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.

  • That's exactly what I was looking for! Makes perfect sense, thank you! – Alexei Andreev Feb 18 '13 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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