

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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?

share|cite|improve this question
up vote 6 down vote accepted

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 analyisis uses the potential function $$ \Phi(F)=|W| +2\cdot \text{# marks}. $$ If we call ExtractMin this might costs $O(|W|)$, 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 cannont 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.

share|cite|improve this answer
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? – Helium Dec 19 '12 at 10:04
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. – A.Schulz Dec 19 '12 at 12:10
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)$. – bellpeace Nov 12 '13 at 4:05

Your Answer


