Marked nodes in Fibonacci heaps

Question

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.

Answer 1

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(2^k) 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.

• Alexei Andreev: That's exactly what I was looking for! Makes perfect sense, thank you!