堆 - 以错误的顺序返回堆

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

堆 - 以错误的顺序返回堆

Heap - returning heap in the wrong order

java

heapsort