﻿ algorithm - algorithm - hi i have question here is pseudo code about sift up and sift down on heaps - oipapio - oipapio.com oipapio

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

i have following pseudo code :

``````void 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;
``````

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

1. 2019-11-14

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.