Downheap sur tableau donnant une mauvaise sortie

Question

J'écris un programme pour exécuter un tri de tas. Lorsque j'essaie d'exécuter la fonction removeMin et un downheap, il semble que je reçois toujours une sortie incorrecte.

Par exemple, si je entrée 10 entiers dans cet ordre:

3, 6, 8, 3, 89, 35, 7, 9, 1, 4 

Je me attends

1, 3, 3, 4, 6, 7, 8, 9, 35, 89 

Mais je reçois:

1, 3, 3, 4, 6, 7, 8, 9, 35, 35 

Voici mon code tas de code:

public class heapsort { 

private Integer[] myHeap; 
private int size; 
private int maxSize; 

public heapsort (int x){ 
    myHeap = new Integer[x+1]; 
    maxSize=x; 
    size=0; 
} 

public void min(){ 
    if (isEmpty()) 
     System.out.print("Is empty"); 
    else 
     System.out.println(myHeap[0]); 
} 

public boolean isEmpty(){ 
    return (size==0); 
} 

public int size(){ 
    return size; 
} 

public void insert(int x){ 
    if (size==maxSize) 
     System.out.println("Heap is full"); 
    else{ 
     size++; 
     myHeap[size] = x; 
     upheap(size); 
    } 
} 

public void upheap(int x){ 
    int temp; 
    if (x>1){ 
     if (myHeap[x]<myHeap[x/2]){ 
      temp = myHeap[x]; 
      myHeap[x]=myHeap[x/2]; 
      myHeap[x/2]=temp; 
      upheap(x/2); 
     } 
    } 
} 

public void removeMin(){ 
    int temp; 
    temp = myHeap[1]; 
    myHeap[1]=myHeap[size-1]; 
    size--; 
    if (size>1){ 
     downheap(1); 
    } 
    System.out.println(temp); 
} 

public void downheap(int x){ 
    int temp; 

    int temp, minIndex, left=2*x, right=2*x+1; 

    if (right>=size){ 
     if (left>=size) 
      return; 
     else 
      minIndex=left; 
    } 

    else{ 
     if (myHeap[left] <= myHeap[right]) 
      minIndex = left; 
     else 
      minIndex = right; 
    } 

    if (myHeap[x] > myHeap[minIndex]){ 
     temp = myHeap[minIndex]; 
     myHeap[minIndex]=myHeap[x]; 
     myHeap[x]=temp; 
     downheap(minIndex); 
    } 
} 

Suivi par mon programme principal:

public static void main (String[] args){ 
    int i=0; 
    Scanner input = new Scanner(System.in); 
    System.out.println("Enter array size: "); 
    int n = input.nextInt(); 

    heapsort myArray = new heapsort(n); 
     System.out.println("Please input integers"); 
    for (i=1; i<=n; i++){ 
     myArray.insert(input.nextInt()); 
    } 

    while (!myArray.isEmpty()){ 
     myArray.removeMin(); 
    } 
} 
} 

Answer 1

Il me semble de quelques pistes que votre genre gouttes un élément en cours, puis imprime le dernier élément deux fois. Si j'entre une taille de tableau de deux et les numéros 3 et 4 (ou 4 et 3), je reçois

3 
3 

Je pense que cela est assez simple cas que vous devriez être en mesure de penser à ce qui se passe dans le removeMin méthode. Votre tableau est [null, 3, 4] (parce que vous n'utilisez jamais le 0e élément) et la taille est 2. Qu'est-ce que temp? Quel élément du tableau copiez-vous dans myHeap[1]? Quel est le nouveau size? Est-ce que downheap(1) sera appelé ou non? Rappelez-vous que les indices sont basés sur 0. Je vous laisse délibérément les réponses, j'espère que vous comprendrez et serez en mesure de réparer votre bug. PS J'ai corrigé ce que je pensais être le bogue. Maintenant, si j'entre une taille de tableau de 3 et les numéros 1 2 3, je reçois

1 
3 
2 

Donc, soit je me suis trompé ou il y a un bug plus là-dedans. J'espère que vous serez en mesure de comprendre. Il est bon de former vos compétences de débogage, ce ne sera pas la dernière fois que vous en aurez besoin.

PPS Votre méthode min est incorrecte, peu importe puisque vous ne l'utilisez pas. Et vous déclarez temp deux fois en downheap() (vous avez probablement déjà découvert qu'il ne compile pas).

Edit: avertissement: spoiler

Stephen O'C, je crois que vous avez trouvé vos bogues maintenant, donc je ne fais pas de mal à votre apprentissage en confirmant ce que vous savez, et quelqu'un d'autre lire peut être intéressé à savoir aussi. Alors voici les bugs que j'ai trouvés et comment les réparer.

La première erreur est dans la méthode removeMin(). Cette ligne

myHeap[1] = myHeap[size - 1]; 

devrait être

myHeap[1] = myHeap[size]; 

Nous voulons déplacer le dernier élément du tas vers le haut.Puisque les éléments sont dans les index 1 throgh size, nous ne devrions pas soustraire 1 de size (si nous avions utilisé le tableau comme 0, size - 1 aurait été correct.Cette erreur a fait manquer tout élément qui se termine en dernier - souvent un . des plus grands éléments

Avec ce correctif, le code pourrait sembler fonctionner correctement, mais maintenant, puis échangé deux éléments dans la sortie triée le bug est dans ces deux lignes de downheap().

if (right >= size) { 
     if (left >= size) 
      return; 

Si right ou left, respectivement, est égal à size, ils pointent toujours à un élément de le tas, donc dans ce cas, nous devons faire l'opération de tamisage et ne peut pas revenir à ce stade. C'est une erreur très similaire à la première. Le correctif consiste à utiliser strict supérieur à des opérateurs:

if (right > size) { 
     if (left > size) 

Avec ce correctif, je n'ai pas détecté d'autres bogues.