Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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