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
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts

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