1

我有一个随机生成数据的测试程序是随机生成的，然后将它们传递给类Sorter的类构造函数。然后 Sorter 会对数据进行排序，并通过一个方法将其传回给 main 函数。我还实现了其他几种排序方法作为 Sorter 类的子类，它们工作得很好。所以我认为我的 Sorter 类没有问题。下面是使用堆排序时我的测试程序的输出。

数据：

48 96 71 81 78 72 93 52 67 70

排序数据：

48 71 81 78 72 67 52 93 70 96

如您所见，经过以下代码后，数据没有排序。下面是代码。

public class HeapSort extends Sorter{
    private int[] heap;
    private int size;

    public HeapSort(int[] data){
        super(data);
    }

    public void sort(){
        constructHeap();

        for(int i = size - 1; i >= 0; i--){
            numbers[i] = extractMax();
        }
    }

    public void constructHeap(){
        size = numbers.length;
        heap = new int[size];
        for(int j = 0; j < size; j++) heap[j] = numbers[j];

        for(int i = size/2 - 1; i >= 0; i--){
            fixHeap(i, heap[i]);
        }
    }

    public int extractMax(){
        int max = heap[0];
        fixHeap(0, heap[--size]);
        return max;
    }

    public void fixHeap(int pos, int key){
        if(left(pos) > size) heap[pos] = key; // if current position is leaf
        else{
            int largest = pos;
            int r = right(pos);
            int l = left(pos);
            if(r < size && heap[largest] < heap[r]) largest = r;
            if(l < size && heap[largest] < heap[l]) largest = l;

            if(largest == pos) heap[pos] = key;
            else{
                heap[pos] = heap[largest];
                fixHeap(largest, key);
            }
        }
    }

    public int left(int i){return 2*i+1;}

    public int right(int i){return 2*i+2;}
}

编辑：下面是调试的代码。希望有人会发现它有用。

public class HeapSort extends Sorter{

  private int[] heap;
  private int size;

  public HeapSort(int[] data){
    super(data);
  }

  public void sort(){
    constructHeap();

    for(int i = size - 1; i >= 0; i--){
      numbers[i] = extractMax();
    }
  }

  public void constructHeap(){
    size = numbers.length;
    heap = new int[size];
    for(int j = 0; j < size; j++) heap[j] = numbers[j];

    for(int i = size/2 - 1; i >= 0; i--){
      fixHeap(i);
    }
  }

  public int extractMax(){
    int max = heap[0];
    heap[0] = heap[--size];
    fixHeap(0);
    return max;
  }

  public void fixHeap(int pos){
    if(left(pos) < size){               // if current position is not leaf
      int largest = pos;
      int r = right(pos);
      int l = left(pos);
      if(r < size && heap[largest] < heap[r]) largest = r;
      if(l < size && heap[largest] < heap[l]) largest = l;

      if(largest != pos){
        exchange(pos, largest);
        fixHeap(largest);
      }
    }
  }

  public int left(int i){return 2*i+1;}

  public int right(int i){return 2*i+2;}

  public void exchange(int a, int b){
    int temp = heap[a];
    heap[a] = heap[b];
    heap[b] = temp;
  }

}
4

1 回答 1

3

我假设你有一个调试器，并且知道如何使用它。

在我看来，调试复杂代码的最佳方式就是我所说的“分而治之的调试”。伪代码：

void debug(Time beforeTheBug, Time afterTheBug) {
    do {
        Time pivot = between(beforeTheBug, afterTheBug);
        if (stateIsAsExceptedAt(pivot)) {
            afterTheBug = pivot;
        } else {
           beforetheBug = pivot;
        }
    } while (amountOfCodeExecutedBetween(beforeTheBug, afterTheBug) is not trivial);
}

在您的情况下，我的第一个检查是输出。确实，它没有排序，所以 bug 就在这个类中。

我的下一个检查是在constructHeap 之后堆不变量是否得到满足。当时，heap是[96, 48, 93, 81, 78, 72, 71, 52, 67, 70]，所以不满足堆不变量（48不大于78），在构造的时候出现bug堆。

查看constructHeap() 没有发现有用的断点，因为第一个循环非常简单，而且不太可能出错，而第二个循环（调用fixHeap）包含所有复杂性。

循环的第一次迭代没有发现任何变化，这是正确的，因为子树已经满足堆不变量。第二次迭代也一样。

第三次迭代正确地识别出右孩子大于根，并交换两者。

第四次迭代没有发现任何改变，这是正确的。

所以它是包含问题的循环的最后一次迭代。两个孩子都比父母大。fixHeap 正确地将较大的孩子移动到根中，并递归调用自身。该调用找到满足的堆不变量，并返回。但是返回后不满足不变量。

所以问题出在从检测堆不变到返回的某个地方。检测检查：

        if (r < size && heap[largest] < heap[r])
            largest = r;
        if (l < size && heap[largest] < heap[l])
            largest = l;

其中heap是 [96, 96, 93, 81, 78, 72, 71, 52, 67, 70]。是的，96 大于 81 和 78。但实际上，不应该heap[pos] == key吗？啊，这就是下一个语句的作用......

换句话说，我们在完成上一次更新之前检查堆不变量，然后完成该更新，这在这种情况下破坏了不变量......

于 2013-10-12T10:18:32.300 回答