CODEWITHSUNDEEP
c++heapsort
Amanda Rose
Amanda Rose

Reputation: 5

Not able to find error in my Heap Sort Code. Not executing properly. C++

Please help. I have reviewed it and seem to be missing the error. It seems to be exiting out of the function Max_Heapify and not running my second loop to print the sorted array. This was for an assignment I have already turned in but I am trying to learn the error of my ways to make sure I can do well on the test. 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

// declare global variable of heap size 
int heap_size = 7;


// function to determine left child node of the tree 
int Left(int i){
    return 2*i+1;
}

// function to determine right child node of the tree 
int Right(int i){
    return 2*i + 2;
}

// create heap tree 
void Max_Heapify (int array[], int index){
    int left_child_index = Left(index);
    int right_child_index = Right(index);
    int largest; 

    // check if left child is smaller than heap size and if left child is bigger than parent
    // if so, save variable as largest value, otherwise, largest value will stay as index
    if ( (left_child_index < heap_size) && (array[left_child_index] > array[index]) )
        largest = left_child_index;
    else largest = index;
    // check if right child is smaller than heap and if bigger than largest value
    if ((right_child_index < heap_size) && (array[right_child_index] > array[largest]) )
        largest = right_child_index;
    // exchange largest values 
    if (largest != index)
        swap(array[index], array[largest]);


    Max_Heapify(array,largest);

}

// check leaves 
void Build_Max_Heap(int array[]){

    for (int i = (heap_size / 2 ) - 1; i >= 0; i--)
        Max_Heapify (array, i);
}


void Heapsort(int array[]) {
    Build_Max_Heap(array);
    for (int i = heap_size-1; i >= 0; i--){
        swap(array[0], array[i]);
        Max_Heapify(array,0);
    }
}

int main(){

    int arr[7] = {21, 9, 50, 7, 6, 33, 77};

    cout << "Non Heapified Array: " << endl;
    for (int i = 0; i < heap_size; i++){
        cout << arr[i] << endl;
    }

    Heapsort(arr);

    for (int i = 0; i < heap_size; i++){
        cout << arr[i]<< endl;
    }


}

Upvotes: 0

Views: 85

Answers (1)

Wander3r
Wander3r

Reputation: 1881

Your MaxHeapify never terminates. You should call MaxHeapify only if largest is not i. If largest is i, then nothing needs to be done here as the elements are already heapified.

if (largest != index){
    swap(array[index], array[largest]);
    Max_Heapify(array,largest);
}

Upvotes: 1

Related Questions