堆-返回顺序错误的堆

Question

我下面的方法是修复堆的顺序。

private void upHeap(int i) {
    // TO DO Implement this method
    int temp = 0;
    int n = heap.length-1;

    for(int j=n;j>0;j--){
        
        if(heap[j]>heap[parent(j)]){                      //if current index is greater than its parent, swap
            temp = heap[j];                         //use a temporary variable to help
            heap[j] = heap[parent(j)];                    
            heap[parent(j)] = temp;
            
            upHeap(heap[parent(j)]);
        }   
    }
      
}

和下面的堆

private void downHeap(int i) {
    // TO DO Implement this method
    int temp = 0;
  
    for(int j=i; j<heap.length; j++){
        if(heap[i]<heap[j]){
            temp = heap[j];
            heap[j] = heap[i];
            heap[i] = temp;
    
        }
    }
        
    
}

它是一个maxHeap，所以数字应该是递减的。有人能从我的代码中看出我哪里出错了吗？它现在给了我一个索引越界错误。

Answer 1

试试这些：

private void upHeap(int i) {
    int temp = 0;

    for (int j = i; j >= 0; j--) {
        for (int k = j - 1; k >= 0; k--) {
            if (heap[j] > heap[k]) {
                temp = heap[j];
                heap[j] = heap[k];
                heap[k] = temp;
            } else {
                break;
            }
        }
    }

}

private void downHeap(int i) {
    int temp = 0;

    for (int j = i; j < heap.length; j++) {
        for (int k = j + 1; k < heap.length; k++) {
            if (heap[k] > heap[j]) {
                temp = heap[j];
                heap[j] = heap[k];
                heap[k] = temp;

            } else {
                break;
            }
        }
    }
}