Proving Correctness of Heap Building Algorithm

[evinda]

Hello! (Nerd)

We are given the following algorithm:

1.BUILDHEAP(A) 
2.    for (i=floor(size(A))/2; i>=0; i--)
3.          HEAPIFY(A,i);

according to my notes, we could prove its correctness, proving the following sentence:

At the beginning of each iteration of the for loop at the lines 2-3, each node $i+1, i+2, \dots, n $ is the root of a max-heap.

Could you explain me why it suffices to prove the above sentence?

Also, how could we prove it? (Thinking)

 

[johng1]

You ignored "heapify". Assuming this is the standard "sift down" algorithm, I don't see that there's much of anything to prove. Sift down produces a heap, starting at the "root".