How can I prove that a build max heap's amortized cost is $O(n)$?

Answered By : A.Schulz

I assume that the operation build just turns an array into a heap by repairing the heap-property for every subtree bottom-up (let the operation for a single repair step called heapify).

It is not so hard to see, that heapify takes $O(h)$ steps, where $h$ is the height of the subtree to repair. We set $k=\lfloor \log n \rfloor $ as the height of heap. Notice that we have no more then $2^{(k-h)}$ subtrees of height $h$. So we can simply add up the costs as follows (we slightly abuse the big-O notation):

$$ \sum_{h=1}^k O(h) 2^{k-h} = 2^k \sum_{h=1}^k O(h)/2^{h}. $$

Since $\sum_{h=1}^\infty O(h)/2^{h}$ converges, we can upper bound the sum $\sum_{h=1}^k O(h)/2^{h}$ by a constant $C$. Thus we have that the running time for built is less than $C\cdot 2^k\le C \cdot n = O(n)$.

Problem Detail: 

Suppose a build max-heap operation runs bubble down over a heap. How does its amortized cost equal $O(n)$?

Asked By : user1675999

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6655