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
algorithm
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