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 | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Make Heap Best Case

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**