question about siftdown operation on heap
- by davit-datuashvili
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
