Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A lower bound of the needed number of comparision to build a heap is given by GASTON H. GONNET and J. IAN MUNRO 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?

share|cite|improve this question
Maybe you can try Computer Science beta. – hengxin Feb 14 '14 at 14:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.