Heap - returning heap in the wrong order

user_15254698 0
Viewed 69

My methods below are to fix the heap order.

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

And the down heap

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

It is a maxHeap, so the numbers should be descending. Can anybody see in my code where I've gone wrong? It is now giving me an index out of bounds error.

heapsort java
1 Answers

Try these:

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