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

Question

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?

Can someone please help me out?

Answer 1

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.

Then for a particular node how much time does heapify take? By definition of depth you can see it is order of depth of the node.

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). $$