patternMinor
Why clear the child's and not the parent's mark in Fibonacci heaps?
Viewed 0 times
whythefibonacciparentchildclearandheapsnotmark
Problem
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:
A reminder of FIB-HEAP-LINK:
FIB-HEAP-LINK($H$, $y$, $x$)
-
Remove $y$ from the root list of $H$
-
Make $y$ a child of $x$, incrementing degree[$x$]
-
Set mark[$y$] to FALSE
- What happens if we leave their marks as is?
- Why clear the child's mark rather than the parent's?
A reminder of FIB-HEAP-LINK:
FIB-HEAP-LINK($H$, $y$, $x$)
-
Remove $y$ from the root list of $H$
-
Make $y$ a child of $x$, incrementing degree[$x$]
-
Set mark[$y$] to FALSE
Solution
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?
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?
Context
StackExchange Computer Science Q#49710, answer score: 6
Revisions (0)
No revisions yet.