配列の出力が間違っている

Question

ヒープソートを実行するプログラムを作成しています。私がremoveMin関数を実行しようとすると、ダウンヒートが発生すると、私は常に間違った出力を得ているようです。例えば

私がこの順に入力10個の整数を場合：

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

私は

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

を期待しかし、私は得る：ここで

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

は、私のコードのヒープコードです：

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); 
    } 
} 

私のメインプログラムが続く：それはあなたの並べ替えが進め一つの要素をドロップした後、二回最後の要素を印刷し、いくつかの実行から私には思える

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

。私は2と番号3の配列のサイズを入力し、4（または4と3）、私は

3 
3 

を取得する場合、私は、これはあなたがremoveMinに何が起こるかを考えることができる必要があり、単純な十分なケースだと思います方法。あなたの配列は[null, 3, 4]です（0番目の要素を決して使用していないため）。サイズは2です。tempは何ですか？どの配列要素をmyHeap[1]にコピーしていますか？新しいsizeとは何ですか？ downheap(1)は呼ばれますか？インデックスは0ベースであることに注意してください。私は意図的にあなたに答えを残しています、私はあなたが把握し、あなたのバグを修正することができると信じています。

PS私はバグだと思ったものを修正しました。私は3と番号1 2 3の配列のサイズを入力すると今、私はそうどちらか私が間違っていた

1 
3 
2 

を取得したり、1つの以上のバグがそこにあります。あなたが把握できることを願っています。デバッグのスキルを磨くのは良いことですが、最後には必要ではありません。

PPS minの方法は間違っていますが、使用していないので問題はありません。そして、あなたはをdownheap()で2回宣言しています（既にコンパイルされていないことが判明しているでしょう）。

編集：警告：スポイラー

スティーブンO'C、私はあなたが今では、あなたのバグを発見したので、私はあなたが知っていることを確認することで、あなたの学習に害を行い、他の誰かいないと信じて一緒に読むことは知っていることに興味があるかもしれません。だから私が見つけたバグとそれを修正する方法があります。

最初のエラーはremoveMin()メソッドにあります。

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

この行は、私たちが先頭に、ヒープの最後の要素を移動したい

myHeap[1] = myHeap[size]; 

でなければなりません。要素はインデックス1 throgh sizeにあるので、sizeから1を引くべきではありません（0ベースの配列を使用していましたが、size - 1は正しいでしょう）。このエラーは、ヒープ内で最後に終了する要素大きな要素の

この修正により、コードが正しく動作しているように見えますが、今してソートされた出力の2つの要素をスワップ可能性がバグがdownheap()次の2行にあります。。

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

rightまたはleftがそれぞれsizeに等しい場合、それらは依然としてヒープなので、この場合、ふるい分け作業を行う必要があり、この時点では戻れません。最初のものと非常に似たエラーです。この修正により、これ以上のバグを発見することができませんでした。この修正により、これ以上のバグは発見できませんでした。