5
$\begingroup$

According to Cormen et al.'s Introduction to Algorithms chapter 21 on Fibonacci heaps (3rd edition), the FIB-HEAP-LINK($H$, $y$, $x$) clears mark of $y$ which will in the end be the child on the resulting merge. I just don't get it, why should we bother clearing this mark? In particular:

  1. What happens if we leave their marks as is?
  2. Why clear the child's mark rather than the parent's?

A reminder of FIB-HEAP-LINK:

FIB-HEAP-LINK($H$, $y$, $x$)

  1. Remove $y$ from the root list of $H$

  2. Make $y$ a child of $x$, incrementing degree[$x$]

  3. Set mark[$y$] to FALSE

$\endgroup$
5
$\begingroup$

To understand Fibonacci heaps, it may help to understand binomial heaps first.

A binomial heap is a forest of heap-ordered binomial trees. A binomial tree of degree k is a node whose children are binomial trees of degree k-1, k-2, ... 0. Note that the number of nodes in a binomial tree of degree k is $2^k$.

If you never do any decrease key operations (or delete operations of nodes other than the minimum), then the Fibonacci heap is a binomial heap.

Conceptually, a Fibonacci tree is a binomial tree which allows for a controlled amount of "damage".

The degree of a Fibonacci heap node is redefined to be the number of children that it has. The structural constraint is designed so that the tree can tolerate a certain amount of deviation from the binomial heap constraint. Most textbooks don't precisely define it, but the key property is this:

Suppose that x is any node in a Fibonacci heap. If you order its children in the order that they were linked to x, then the ith child has a degree at least i-2. If it has degree equal to i-2, the node must be marked. If it is greater than i-2, then it may or may not be marked.

In particular, a mark signifies that a node may be one degree too "small" for its parent. (Note that this property is almost lemma 1 from the original paper.)

The first thing to notice is that when we cut a node, we unmark it. The reason for this should be obvious: it has no parent, so it can't possibly be too "small".

Now think about the link operation. We only ever link two nodes together if they have the same degree. Let's suppose that d is the degree of x and y, and we want to make x the new parent of y.

Since we are adding a child to x, so this changes the degree of x to d+1. The node y is the (d+1)th child linked to x, so to preserve the structural constraint, it must be marked if it has degree d-1. However, by construction it has degree d. It is not too "small", so we unmark it.

Of course, the structural constraint is preserved whether or not y is marked. Why, then, do we clear the mark? Intuitively, it's because encountering a mark during an unlink operation triggers a cascading cut. We want to avoid those, so we want to have as few nodes marked as possible. At any point, if we can tell that a node doesn't have to be marked, we make sure it's not marked.

Did that help?

$\endgroup$
  • $\begingroup$ I have some comments, first You said "it has no parent, so it can't possibly be too "small"." is the reason why roots are cleared on cut, but then how come you can make a root be marked with some play with Min-Extracts and Decrease-Keys? is this a bug that doesnt have influence on time complexity, or is it a wanted property? $\endgroup$ – Ofek Ron Nov 20 '15 at 8:04
  • $\begingroup$ It did help, but as i said, the fact that they clear marks on tree merges rather than whenever a node becomes a root is very unclear to me. They should have cleared all marks of children of min when doing extract min, it could be way more clear and intuitive. it would work right? $\endgroup$ – Ofek Ron Nov 20 '15 at 8:12
  • $\begingroup$ You could clear a mark on a node when it becomes a root, or you could do it when it is relinked. Either way works; I suppose you could do it the other way. Interestingly, if you read the paper, the potential function used to justify the amortised running time is the number of trees plus twice the number of marked non-root nodes. Marked root nodes don't matter to the time analysis at all. $\endgroup$ – Pseudonym Nov 27 '15 at 4:44

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.