Построение кучи снизу вверх

Question

Я пытаюсь сделать конструкцию "куча снизу вверх" из кода Psuedo из моего учебника, однако вывод, который я получаю, не является правильной кучей, которую я получаю 2 9 8 6 5 7

Кто-нибудь знает, где я иду не так (псевдокод из учебника, а куча должна быть массив)

вот PsuedoCode снизу вверх, я работаю с

//constructs a heap from elements of a given array by bottom up algorithm
//input an array H[1...n] of orderable items
//output a heap H[1...n]

for i<- [n/2] downto 1 do
 k<-i; v<-H[k];
 heap<-False
  while not heap and 2*k <= n do
   j<-2*k
   if(j<n) //there are two children
    if H[j] < H[j+1] j<- j+1
   if v>=h[j]
    heap = true
   else H[k]<-H[j]  k<-j
 H[k] <-V

вот мой код

package heapbottomup;

import javax.swing.Spring;

public class heapbottomup {
public static void main(String args[]){
    int[] array = {2 ,9 ,7 ,6 ,5 ,8};
    BottomUp(array);
}

static int[] BottomUp (int[]array){
    int n = array.length-1;

    for(int i=(n/2);i>=1;i--){
        int k =i;
        int v = array[k];
        boolean Heap = false;

        while(!Heap && ((2*k)<=n)){
            int j = 2*k;
            if (j<n){
                if(array[j]<array[j+1]) j =j+1;
            }
            if(v>=array[j]){
                Heap=true;
            }
            else{
                array[k]= array[j];
                k=j;
            }
            array[k]=v;
        }//end while

    }//end for
    print(array);
    return(array);
}


static void print(int[]array){
    if(array==null){
        System.out.println("empty");
        return;
    }
    for(int i =0;i<array.length;i++){
        System.out.print(array[i] + " ");
    }
    System.out.println();
}//end print


}

Answer 1

Ключевые моменты:

• Чтобы сохранить свойство узла в позиции j, что его левый дочерний элемент находится в 2j, его правый дочерний элемент - в 2j +1, а его родительский элемент - в j/2, диапазон j составляет: 1<=j<=n,
• Диапазон массива от 0 до n-1

Хитрость заключается в следующем: в циклах for и while вы по-прежнему думаете о диапазоне от 1 до n, но когда вы выполняете манипуляции с массивами, вам нужно только сместить 1, то есть массив [j-1] для позиции j.

Попробуйте использовать следующий код, который я протестировал, и он сработал - вывод 9 6 8 2 5 7. Обратите внимание, что массив [k-1]=v не находится в цикле while.

public class heapbottomup {
    public static void main(String args[]){
        int[] array = {2 ,9 ,7 ,6 ,5 ,8};
        BottomUp(array);
    }

    static int[] BottomUp (int[]array){
        int n = array.length;

        for(int i=(n/2);i>=1;i--){
            int k =i;
            int v = array[k-1];
            boolean Heap = false;

            while(!Heap && ((2*k)<=n)){ 
                int j = 2*k;
                if (j<n){
                    if(array[j-1]<array[j]) j =j+1;
                }
                if(v>=array[j-1]){
                    Heap=true;
                }
                else{
                    array[k-1]= array[j-1];  
                    k=j; 
                }                
            }//end while

            array[k-1]=v; 

        }//end for
        print(array);
        return(array);
    }

    static void print(int[]array){
        if(array==null){
            System.out.println("empty");
            return;
        }
        for(int i =0;i<array.length;i++){
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }//end print
}

Answer 2

Массивы в Java начинаются с индекса 0 и перейти к n-1 (не от 1 до n, как в псевдокоде). Вы правильно инициализируете array.length-1, но тогда вы должны также сделать цикл for i >= 0 не i >= 1, Я не запускал вашу программу, чтобы увидеть, есть ли другие проблемы, но это, кажется, первое, что нужно исправить.