H
HansPeterLoft
Gast
Hallo,
ich versuche einen Heap zu implementieren, die insert() Funktion funktioniert,
jedoch getMin() gibt einen ArrayIndexOutOfBOundException.
Ich verstehe aber einfach nicht was daran falsch ist:
Zur Theorie:
Man nimmt den letzen Knoten des untersten Niveaus und ersetzt damit die Wurzel.
Dann schaut man ob einer der zwei Nachkommen kleiner als der Knoten ist:
Knoten k, Nachkommen 2k, 2k+1; Falls Ja -> kleineren vertauschen.
ich versuche einen Heap zu implementieren, die insert() Funktion funktioniert,
jedoch getMin() gibt einen ArrayIndexOutOfBOundException.
Ich verstehe aber einfach nicht was daran falsch ist:
Java:
import java.util.*;
public class HeapSort {
void insert(int x, int [] list, int size) { //falls k-1 statt k/2 -> insertion Sort
int k = size + 1; //1 wegen getMin(), sonst wäre 2+k nicht möglich
while (x <= list[k/2] && k>1) {
list[k] = list[k/2];
k = k/2;
} list[k] = x;
}
int getMin(int [] list) {
int returnValue = list[1];
int size = list.length;
int k = 1;
list[k] = list[size-1];
int w = list[1];
while(list[2*k] < list[k] || list [2*k + 1] < list[k]) {
boolean b = (list[2*k] > list[2*k + 1]);
if(b) {
list[k] = list[2*k + 1];
list[2*k + 1] = w;
k= k*2 + 1;
} else {
list[k] = list[2*k];
list[2*k] = w;
k = k*2;
}
}
return returnValue;
}
}
Zur Theorie:
Man nimmt den letzen Knoten des untersten Niveaus und ersetzt damit die Wurzel.
Dann schaut man ob einer der zwei Nachkommen kleiner als der Knoten ist:
Knoten k, Nachkommen 2k, 2k+1; Falls Ja -> kleineren vertauschen.
Zuletzt bearbeitet von einem Moderator: