- #1
khdani
- 55
- 0
Hello,
I don't understand the proof of best case for Make Heap algorithm.
The Algorithm is:
while the procedure Sift_Down is:
the proof for the best case goes like this:
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
I don't understand the proof of best case for Make Heap algorithm.
The Algorithm is:
Code:
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]
while the procedure Sift_Down is:
Code:
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;
the proof for the best case goes like this:
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
Last edited: