Привет у меня есть вопрос, вот псевдокод просеивать и просеивать на кучах

Question

у меня следующий псевдокод:

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;

, пожалуйста, помогите мне написать его в реальном коде. У меня есть вопрос о цикле, например, где находится начальная точка цикла?

У меня есть doenэто и правильно ли?открытый класс siftup {

открытый статический void main (аргументы String []) {

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];а [р] = а [I];а [I] = т;} i = p; </p>

}

для (int j = 0; j

}} // результат равен 15 20 19 29 23 12 22 35 40 26 51 17

Answer 1

Если h является вашей кучей и является максимальной-кучей, ее индексирован от 0, а n - количество элементов, то это должно работать:

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;
}

У меня есть вопрос о цикле, например, где находится начальная точка цикла?

Цикл начинается с последнего элемента массива кучи, так как обычно это тот, который вы хотите переместить в нужную позицию.