1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You can use LaTeX in your answers (and questions). $\endgroup$ – Yuval Filmus May 6 '14 at 19:48
  • $\begingroup$ @Sayan Thats a great answer, thanks a lot for your help. $\endgroup$ – eager2learn May 6 '14 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.