hi i have question here is pseudo code about sift up and sift down on heaps

i have following pseudo code :

v开发者_JAVA技巧oid siftup(int n)
 pre condition n>0  && heap(1,n-1)
post heap(1,n)
 i=n;
 loop
/* invariant: heap(1,n)   except  perhaps 
  between    i and   its parent 
 if (i==1)
   break;
 p=i/2;
 if (x[p]<=x[i])
   break;
 swap(p,i);
i=p;

please help me to write it in real code i have question about loop for example where is starting point of loop?

i have doen this and is it correct? public class siftup {

public static void main(String[]args) {

int p;

int n=12; int a[]=new int[]{15,20,12,29,23,17,22,35,40,26,51,19};

int i=n-1; while (i!=0) {

if (i==1) break;

p=i/2; if (a[p]<=a[i]){ int t=a[p]; a[p]=a[i]; a[i]=t; } i=p;

}

for (int j=0;j

} } //result is this 15 20 19 29 23 12 22 35 40 26 51 17

---

If h is your heap and is a max-heap, its indexed from 0, and n is the number of elements, then this should work:

int position = n - 1;
while (position > 0 && h[(position - 1) / 2] <= h[position]) // while the parent of the current node is smaller than the current child, swap it with its child (only in case of a max-heap, it's the other way around for a min-heap)
{
    swap(h[(position - 1) / 2] = h[position]);
    poistion = (position - 1) / 2;
}

i have question about loop for example where is starting point of loop?

The loop starts with the last element of the heap array, as that is usually the one you want to move to the right position.