la création d'un max-tas à l'aide de java
Je suis en train de créer un Max de Tas en java en utilisant le code suivant:
public class Heapify {
//16 14 10 8 7 9 3 2 4 1
public static int[] Arr = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
public static int counter = 0;
public static void main(String[] args) {
int kk;
for (kk = 0; kk <= Arr.length - 1; kk++) {
heapM(Arr, kk);
}
for (int krk = 0; krk < Arr.length; krk++) {
System.out.println(Arr[krk]);
}
}
public static void heapM(int[] Arr, int i) {
int largest;
int left = i * 2;
int right = i * 2 + 1;
if (((left < Arr.length) && (Arr[left] > Arr[i]))) {
largest = left;
} else {
largest = i;
}
if (((right < Arr.length) && (Arr[right] > Arr[largest]))) {
largest = right;
}
if (largest != i) {
swap(i, largest);
heapM(Arr, largest);
}
}
private static void swap(int i, int largest) {
int t = Arr[i];
Arr[i] = Arr[largest];
Arr[largest] = t;
}
}
La sortie désirée doit être :
16 14 10 8 7 9 3 2 4 1
Alors que je suis arriver
4 3 16 14 8 9 10 2 1 7
Quelqu'un peut s'il vous plaît aider pourquoi le tas n'est pas construit correctement ?
Grâce
S'il vous plaît poster des extraits de code indenté lisible.
Grâce Sujay pour la mise en forme , Millimoose désolé pour le format raw
Grâce Sujay pour la mise en forme , Millimoose désolé pour le format raw
OriginalL'auteur Satya | 2012-07-17
Vous devez vous connecter pour publier un commentaire.
J'ai couru votre code, et en plus de ce Jodaka dit, j'ai trouvé encore une erreur
devrait être
parce que quand vous faites MaxHepify, vous commencez par la fin, et revenir en arrière.
et
doit être, comme Jodaka dit
J'ai couru ici et la sortie est maintenant correct
merci beaucoup La Bla Bla , vous avez sauvé ma vie 🙂
content d'avoir pu aider 🙂 Bonne chance
OriginalL'auteur La bla bla
Je pense que votre problème est ici:
Depuis java les tableaux sont basés sur zéro, vous dites que la gauche de l'enfant de 0 est 0 * 2 = 0! Fixer votre logique et voir si cela résout votre problème.
Mon point est que vous ne faites pas de calcul les enfants correctement pour n'IMPORTE quel nœud. Je viens d'utiliser 0 comme l'exemple le plus évident.
Eu Jodaka , merci beaucoup , you rock !!
OriginalL'auteur Jodaka
devrait être
Plus efficace.
Modifier Cela vous permet de construire un segment de mémoire en O(n) au lieu de O(n*lg(n)) et le temps est expliqué ici: http://en.wikipedia.org/wiki/Binary_heap#Building%5Fa%5Fheap
OriginalL'auteur stones333
Que vous voulez faire un max-heap, vous devriez commencer à partir de n/2 à 0 au lieu de 0 à n. En raison de 0 à n ce qui se passe, c'est que dire dans un tableau comme 2 0 1 12 13. Le tableau de sortie une fois que vous effectuez max tas sera 2 13 1 12 0, où comme si vous appelez à partir de n/2 à 0, il sera 13 12 1 2 0.
OriginalL'auteur Egalitarian
Est-ce un devoir?
Si non, vous pouvez utiliser PriorityQueue de JAVA
ok grand sens
OriginalL'auteur javanx