Hello,(adsbygoogle = window.adsbygoogle || []).push({});

I don't understand the proof of best case for Make Heap algorithm.

The Algorithm is:

while the procedure Sift_Down is:Code (Text):

Make_Heap(M[1...n])

[INDENT]

for i= [tex]\left\lfloor n/2 \right\rfloor[/tex] to 1

[INDENT]

Sift_Down(M[1...],i);

[/INDENT]

[/INDENT]

the proof for the best case goes like this:Code (Text):

Sift_Down(M[1...n],i)

k=i;

repeat

[INDENT]

j=k;

if 2j [tex]\leq[/tex] n and M[2j] > M[k] then k=2j;

if 2j < n and M[2j+1] > M[k] then k=2j+1;

Exchange M[k] and M[j]

[/INDENT]

until k = j;

t(n) <= 2*2[tex]^{0}[/tex] + 2*2[tex]^{1}[/tex] + ... + 2*2[tex]^{k-2}[/tex]

so why not until 2[tex]^{k-1}[/tex], in Make_Heap procedure it iterates till the root ?

and why every term is multiplied by 2 ?

Thank You

**Physics Forums - The Fusion of Science and Community**

# Make Heap Best Case

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

Have something to add?

- Similar discussions for: Make Heap Best Case

Loading...

**Physics Forums - The Fusion of Science and Community**