<p>It is essentially using decision tree model to obtain the lower-bound. There are $n!/H(n)$ leafs in the decision tree, it is a binary tree, therefore the height of the tree is at least $\lg (n!/H(n))$.</p>

CC BY-SA 3.0
2013-03-02T07:10:29.530Z
2013-03-02T07:10:29.530Z
Kaveh
<p>A lower bound of the needed number of comparision to build a <a href="http://en.wikipedia.org/wiki/Heap_%28data_structure%29" rel="nofollow">heap</a> is given by <a href="http://epubs.siam.org/doi/pdf/10.1137/0215068" rel="nofollow">GASTON H. GONNET and J. IAN MUNRO</a> as following</p>

<blockquote>
  <p>THEOREM 4. $1.3644... n + O(lg n)$ comparisons are necessary, not only in the worst
  case, but also on the average to create a heap on n elements.</p>
  
  <p>Proof - A reasonably straightforward enumeration shows that there are $H(n)=
n !/\prod t_i$ valid heaps on a set on n numbers where $t_i$ is the size of the heap rooted at
  node $i$. A lower bound on the average number of comparisons required to permit one
  of $n!$ possible input sequences to one of these orders is $$\lg(n!/H(n))=\sum \lg t_i.$$</p>
</blockquote>

<p>I understand how the number of valid heap is calculated. But I don't know information theory so I can't see how the last equation is the lower bound. Is there any theorem or book I can check to see how this works?</p>

CC BY-SA 3.0
2013-03-02T07:08:38.030Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.
Kaveh
<ds.algorithms>
Lower bound of the time complexity of heap building
LeafGlowPath
# Lower bound of the time complexity of heap building

(Asked by: username_0 on 2013-03-01)

A lower bound of the needed number of comparision to build a [heap](http://en.wikipedia.org/wiki/Heap_%28data_structure%29) is given by [GASTON H. GONNET and J. IAN MUNRO](http://epubs.siam.org/doi/pdf/10.1137/0215068) as following

> THEOREM 4. $1.3644... n + O(lg n)$ comparisons are necessary, not only in the worst
> case, but also on the average to create a heap on n elements.
>
> Proof - A reasonably straightforward enumeration shows that there are $H(n)=
> n !/\prod t\_i$ valid heaps on a set on n numbers where $t\_i$ is the size of the heap rooted at
> node $i$. A lower bound on the average number of comparisons required to permit one
> of $n!$ possible input sequences to one of these orders is $$\lg(n!/H(n))=\sum \lg t\_i.$$

I understand how the number of valid heap is calculated. But I don't know information theory so I can't see how the last equation is the lower bound. Is there any theorem or book I can check to see how this works?

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.  

---

## 1 answers

### Answer by username_1 on 2013-03-02. Score: 0 | Accepted answer

It is essentially using decision tree model to obtain the lower-bound. There are $n!/H(n)$ leafs in the decision tree, it is a binary tree, therefore the height of the tree is at least $\lg (n!/H(n))$.


---

