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?


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.

  • $\begingroup$ Thanks A.Schulz. It seems reasonable to me but I need to think more about it. My other question is that why we need to cut the parent at all? since its key is larger than the grandpa (i.e., it doesn't violate the structure of the heap)? Is it related to the fact that we need to maintain O(log n) children for each node? $\endgroup$ – Helium Dec 19 '12 at 10:04
  • $\begingroup$ If we decrease the key, then the heap-property might be violated. We can either cut (as done in Fibonacci heaps), or we bubble-up and repair the heap-property as done in Binomial heaps. $\endgroup$ – A.Schulz Dec 19 '12 at 12:10
  • $\begingroup$ Just an aside comment/question. If we cut the parent only when it loses the second child, would that improve $W$? I guess not; it should stay $O(\log n)$. $\endgroup$ – bellpeace Nov 12 '13 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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