What is the purpose behind marking some of the nodes in Fibonacci heap?

Question

This picture from Wikipedia article has three nodes of a Fibonacci heap marked in blue . What is the purpose of some of the nodes being marked in this data structure ?

Yogh

Marking is used as a heuristic to achieve good amortized running time on the DecreaseKey operation. By the way, CLRS's chapter on Fibonacci heaps is much better than the Wikipedia article, you should check it. – Precession

@Precession I checked out CLRS also . Still not clear on this marked flag and why it is required ...can you please provide a concrete answer on why we require a marked flag as an heuristic ..I am looking for some intuition here . – Yogh

Answer 1

A node is marked when one of its child nodes is cut because of a decrease-key. When a second child is cut, the node also cuts itself from its parent. Marking is done so that you know when the second cut occurs.

Kassandrakassaraba

"When a second child is cut, the node also cuts itself from its parent. " what happens to the marked status of the node in that case? you also wrote "Marking is done so that you know when the second cut occurs." Can you explain how ho do I know that it is second cut and not the first cut ? – Yogh

1. It becomes unmarked. 2. If you cut a child of a marked node you know it is the second cut. The first cut caused the node to be marked. – Kassandrakassaraba

Answer 2

Intuitively, the Fibonacci heap maintains a collection of trees of different orders, coalescing them when a delete-min occurs. The hope in constructing a Fibonacci heap is that each tree holds a large number of nodes. The more nodes in each tree, the fewer the number of trees that need to be stored in the tree, and therefore the less time will be spent coalescing trees on each delete-min.

At the same time, the Fibonacci heap tries to make the decrease-key operation as fast as possible. To do this, Fibonacci heaps allow subtrees to be "cut out" of other trees and moved back up to the root. This makes decrease-key faster, but makes each tree hold fewer nodes (and also increases the number of trees). There is therefore a fundamental tension in the structure of the design.

To get this to work, the shape of the trees in the Fibonacci heap have to be somewhat constrained. Intuitively, the trees in a Fibonacci heap are binomial trees that are allowed to lose a small number of children. Specifically, each tree in a Fibonacci heap is allowed to lose at most two children before that tree needs to be "reprocessed" at a later step. The marking step in the Fibonacci heap allows the data structure to count how many children have been lost so far. An unmarked node has lost no children, and a marked node has lost one child. Once a marked node loses another child, it has lost two children and thus needs to be moved back to the root list for reprocessing.

The specifics of why this works are documented in many introductory algorithms textbooks. It's not obvious that this should work at all, and the math is a bit tricky.

Hopefully this provides a useful intuition!

Gomez

Answer 3

Good Explanation from Wiki: Operation decrease key will take the node, decrease the key and if the heap property becomes violated (the new key is smaller than the key of the parent), the node is cut from its parent. If the parent is not a root, it is marked. If it has been marked already, it is cut as well and its parent is marked. We continue upwards until we reach either the root or an unmarked node. Now we set the minimum pointer to the decreased value if it is the new minimum.

Attach