question about siftdown operation on heap

Posted by davit-datuashvili on Stack Overflow See other posts from Stack Overflow or by davit-datuashvili
Published on 2010-05-24T12:03:39Z Indexed on 2010/05/24 12:11 UTC
Read the original article Hit count: 172

Filed under:

i have following pseudo code which execute siftdown operation on heap

array suppose is x

void siftdown(int n)
  pre  heap(2,n) && n>=0
 post heap(1,n)
 i=1;
loop    
/*invariant   heap(1,n)   except perhaps between  i and   it's (0,1,or 2) children*/
c=2*i;
 if (c>n)
  break;
// c is left child  of i
 if (c+1)<=n
 /* c+1 is rigth child of i
 if (x[c+1]<x[c])
c++
 /* c is lesser child of i
 if (x[i]<=x[c])
  break;
swap(c,i)
i=c;

i have wrote following code is it correct?

public class siftdown{

public static void main(String[]args){
int c;
int n=9;
int a[]=new int[]{19,100,17,2,7,3,36,1,25};
int i=1;
 while (i<n){
c=2*i;
 if (c>n)
  break;
//c is the left child of i
  if (c+1<=n)
   //c+1 ir rigth child of i
 if (a[c+1]<a[c])
  c++;
 if (a[i]<=a[c])
  break;
  int t=a[c];
   a[c]=a[i];
a[i]=t;

i=c;
}

 for (int j=0;j<a.length;j++){
 System.out.println(a[j]);
}

}
}

// result is

19 2 17 1 7 3 36 100 25

© Stack Overflow or respective owner

Related posts about algorithm