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 $Ccdot 2^kle 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