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.
1