# Show that the running time of the build_heap function is $O(n)$

Given the following two functions, prove that the build_heap function, which transforms an array A into a max-heap-sorted array A' runs in $O(n)$.

heapify(A, i):

Input: array A of length n, index i

left = 2i + 1 (left child node)
right = 2i + 2 (right child node)
largest = i if left < n and A[left] > A[i] then
largest = left
end if
if right < n and A[right] > A[largest] then
largest = right end
if if largest != i then
swap(A, i, largest)
heapify(A, largest)
end if

build_heap(A):

Input: Array of length n

for i = floor((n-1)/2) to 0 do
heapify(A, i)
end for


Hint: Assume that A has $2^j-1$, for $j \in \mathbb{N}$, elements. You can also use the fact that $\sum_{k=0}^{\infty}\frac{k}{2^k} = 2$.

I don't really understand why the formula is given in the hint, or rather how to explicitly use it to prove that build_heap(A) runs in $O(n)$.

I would say that the worst case for the heapify function is given when a call of heapify(A,0) calls itself recursively as much as possible. I think a binary tree with n nodes has depth of $\lceil lg(n) \rceil$, so the maximum number of recursive calls should be $\lceil lg(n) \rceil$.

I'm not sure but my guess is that the formula is trying to tell me that the running time of heapify is $O(1)$? But I don't really see how that's possible. If it were a constant then clearly build_heap(A)` would run in $O(n)$, but how can it be constant?

The main point is to do the analysis exactly without being sloppy. Let me define the depth of a node in this way. Depth of any leaf is 0 and depth of any non-leaf node is maximum depth among its children plus 1. One can note that depth = $\log n -$ height.
Now the total time for buildheap is $$\sum_{d=0}^{\log n} \text{(number of nodes of depth d)}\cdot O(d).$$
Now my claim is that there are at most $n/2^d$ nodes at depth $d$ (can you see why?). For example number of leaves (depth 0) is at most $n/2^0 = n$.
Then, building time is $$\sum_{d = 0}^{\log n} \frac{n}{2^d} \cdot O(d) = O(n)\cdot\sum_{d = 0}^\infty \frac{d}{2^d} = O(n) \cdot 2 = O(n).$$