Register to reply

Make Heap Best Case

by khdani
Tags: case, heap
Share this thread:
khdani
#1
May23-08, 07:23 AM
P: 55
Hello,
I don't understand the proof of best case for Make Heap algorithm.

The Algorithm is:
Make_Heap(M[1...n])
for i= [tex]\left\lfloor n/2 \right\rfloor[/tex] to 1
Sift_Down(M[1...],i);
while the procedure Sift_Down is:
Sift_Down(M[1...n],i)
k=i;
repeat
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]
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
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker

Register to reply

Related Discussions
Heap Pumps, Electrical Energy General Physics 21
The shape of a heap of sand turns flat after being kicked... Quantum Physics 0
Irritating heap corruption error in VC++2005 Programming & Computer Science 0
Learn the general case first, or the special case first? General Math 6
The Sorites heap paradox General Discussion 8