5
$\begingroup$

In CLRS's Introduction to Algorithms 3rd edition P.525, when it analyzes the size($x$)'s lower bound, there is a sentence that I quote as "because adding children to a node cannot decrease the node’s size, the value of $s_k$ increases monotonically with $k$". But in fact, I think I can give a counterexample to show that $s_k$ does not necessarily increase monotonically with k.

In the following graph, the degree of the node with key 1 is 2, and there is no other node with degree of 2. So $s_2=8$. Similarly, $s_3=6$. But now $s_3$ is less than $s_2$ which means $s_k$ is not monotonically increasing with $k$ at all.

2 - 0 - 4 - 2 - 5 - 8 - 7 -  1
            |               /  \
            8              2    9
                              / | \
                             10 14 16
                             |  |
                             11 15

The heap can be derived from an unordered binomial subtree by executing a series of cuts and cascading-cuts.

I want to know whether the above structure is a valid Fibonacci heap. If so, then it is also a valid counterexample.

$\endgroup$
12
$\begingroup$

In CLRS, $s_k$ is defined to be "the minimum possible size of any node of degree $k$ in any Fibonacci heap." Assuming your example data structure is a valid Fibonacci heap, your Fibonacci heap has a node of degree 2 with size 8 and a node of degree 3 with size 6. Thus, these are possible sizes that nodes of degree 2 and 3 can have but not lower bounds on their sizes.

Using Lemma 19.1 (as in the proof of Lemma 19.4), $s_2 = 3$ and $s_3 = 5$, monotonically increasing as CLRS claim.

$\endgroup$

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.