What is the purpose of Mark field in Fibonacci Heaps?

Question

In Fibonacci heaps, we keep a mark field for every node in the heap. Initially all the nodes are unmarked. Once a node is deleted, its parent is marked. If a node is deleted and its parent is already marked, the parent will be cut and inserted into the root list. I just wonder what the purpose of marking is? What happens if we cut the parent just the first time without marking it? Does it change the time complexity of the operations? How?

Answer 1

It does change the complexity of the operations. Simply speaking, the root list $W$ gets too large.

We have two expensive operations, which are ExtractMin and DecreaseKey. Remember that the amortized analysis uses the potential function $$ \Phi(F)=|W| +2\cdot \text{# marks}. $$ If we call ExtractMin this might cost $O(\left|W\right|)$, however after the operation, the root list has only size $O(\log n)$, and we have charged most of the costs to the potential. The question now is how to charge-up the potential. Here come the DecreaseKey operations into play. They are responsible for a large root list $W$. Say, we add $k$ trees to the root list $W$ during the DecreaseKey operation. This means that we remove $k-1$ marks, and we pay with the marks the costs of DecreaseKey and the change of the potential function (that is why we have a factor 2 for the marks in $\Phi$).

So what happens if we immediately put a vertex into the root list when decreasing the key. Then of course the root list might get large. But this is not the problem. The problem is, that you cannot show that after the repair-part of ExtractMin $W$ has at most $O(\log n)$ elements. If I am not mistaken the size of $W$ can then contain up to $\Omega(\sqrt{n})$ elements. That means that if we delete directly the DecreaseKey operations are in $O(1)$ and their worst-case running time is even better than for Fibonacci heaps, but the ExtractMin is $O(\sqrt{n})$.

Another softer perspective is the following: The marks guarantee that you only delete one child for every node. Without deletion every tree in a Fibonacci heap is a binomial tree. The marks ensure that we do not diverse from the binomial tree structure too much.