阵列上给出的错误输出错误

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) 

有了此修复程序，我一直无法发现任何更多的错误。