<p>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.</p>

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

CC BY-SA 3.0
2011-09-03T13:50:52.017Z
2011-09-03T22:13:57.303Z
2011-09-03T22:13:57.303Z
Tyson Williams
<p>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.</p>

<p>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.</p>

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

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

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

<ds.algorithms>
CLRS's Fibonacci Heap size(x) analysis has a flaw?
jscoot
# CLRS's Fibonacci Heap size(x) analysis has a flaw?

(Asked by: username_0 on 2011-09-03)

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.

**Tags:** ds.algorithms


---

## 1 answers

### Answer by username_1 on 2011-09-03. Score: 12 | Accepted answer

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.


---

