陣列上給出的錯誤輸出錯誤

Question

我正在編寫一個程序來執行堆排序。當我嘗試執行removeMin函數和downheap時，似乎總是會得到不正確的輸出。

例如，如果在此爲了我輸入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

在我看來，從您的排序正在進行下降一個元素的幾個運行，然後打印的最後一個元素的兩倍。如果我輸入的兩個數字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 

所以無論是我錯了或者有一個以上的錯誤在那裏。希望你能弄清楚。訓練你的調試技巧是很好的，這不會是你最後一次需要它們的時候。

PPS您的min方法錯了，沒關係，因爲您沒有使用它。並且您在downheap()中聲明temp兩次（您可能已經發現它不能編譯）。

編輯：警告：擾流板

斯蒂芬O'C，我相信你現在發現你的錯誤，所以我不通過確認你知道什麼做任何傷害你的學習，和別人一起閱讀也許也有興趣知道。所以這裏是我發現的錯誤以及如何修復它們。

第一個錯誤是在removeMin()方法中。這條線

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

應該

myHeap[1] = myHeap[size]; 

我們要堆的最後一個元素移動到頂部。由於元素位於索引1ththh size中，所以我們不應該從size中減去1（如果我們將數組用作基於0的數據，那麼size - 1就是正確的。這個錯誤導致堆中最後一個要錯過的元素 - 通常是一個元素。越大的元素

用此修復程序，代碼可能出現正常工作，但現在，然後換入排序輸出兩個元素的錯誤是在downheap()這兩行：

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

如果right或left分別等於size，則它們仍指向堆，所以在這種情況下，我們需要進行篩選操作，並且此時不能返回。這是一個與第一個非常相似的錯誤。解決方法是使用嚴格比運營商嚴格：

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

有了此修復程序，我一直無法發現任何更多的錯誤。