Построение кучи снизу вверх
Я пытаюсь сделать конструкцию "куча снизу вверх" из кода 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
}
2 ответа
Ключевые моменты:
- Чтобы сохранить свойство узла в позиции 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
}
Массивы в Java начинаются с индекса 0
и перейти к n-1
(не от 1 до n, как в псевдокоде). Вы правильно инициализируете array.length-1
, но тогда вы должны также сделать цикл for i >= 0
не i >= 1
, Я не запускал вашу программу, чтобы увидеть, есть ли другие проблемы, но это, кажется, первое, что нужно исправить.