The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al

The authors deal with a notion of marking the nodes of Fibonacci Heaps with the background that they are used to bound the amortized running time of the $\text{Decrease-Key}$ or $\text{Delete}$ algorithm, but not much intuition is given behind their use of it.

What things shall go bad if we do not use markings ? (or) use $\text{Cacading-Cut}$ when the number of children lost from a node is not just $2$ but possibly more ?

The excerpt corresponding to this is as follows:

We use the mark fields to obtain the desired time bounds. They record a little piece of the history of each node. Suppose that the following events have happened to node $x$:

  1. at some time, $x$ was a root,
  2. then $x$ was linked to another node,
  3. then two children of $x$ were removed by cuts.

As soon as the second child has been lost, we cut $x$ from its parent, making it a new root. The field $mark[x]$ is true if steps $1$ and $2$ have occurred and one child of $x$ has been cut. The Cut procedure, therefore, clears $mark[x]$ in line $4$, since it performs step $1$. (We can now see why line $3$ of $\text{Fib-Heap-Link}$ clears $mark[y]$: node $у$ is being linked to another node, and so step $2$ is being performed. The next time a child of $у$ is cut, $mark[y]$ will be set to $\text{TRUE}$.)

[The intuition of why to use the marking in the way stated in italics portion of the block above was made clear to me by the lucid answer here, but I still do not get the cost benefit which we get using markings what shall possibly go wrong if we do not use markings, the answer here talks about the benefit but no mathematics is used for the counter example given]

The entire corresponding portion of the text can be found here for quick reference.


Your Answer

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

Browse other questions tagged or ask your own question.