mardi 12 avril 2022

Max Heap not sorting properly

I am new to sorting algorithms and I'm having a hard time figuring out what is wrong with my Heap sorting code, I built the heap and it returns the expected heap(max value as the root), but when I add another function for sorting and ejecting the last index in my array, it's not sorting properly. please refer to the code below.

#include <iostream>

using namespace std;

void heap(int arr[], int n, int x){
    int parent = x;
    int l_child = x * 2 + 1;
    int r_child = x * 2 + 2;
    
    if(l_child < n && arr[l_child] > arr[parent])
        parent = l_child;
    
    if(r_child < n && arr[r_child] > arr[parent])
        parent = r_child;
        
    if(parent != x){
        int temp = arr[x];
        arr[x] = arr[parent];
        arr[parent] = temp;
        
        heap(arr, n, parent);
    }
}

void buildheap(int arr[], int n){
    for(int x = n / 2 - 1; x >= 0; x--)
        heap(arr, n, x);
}

void sortheap(int arr[], int n){
    for(int x = n - 1; x > 0; x--){
        int temp = arr[0];
        arr[0] = arr[x];
        arr[x] = temp;
        
        heap(arr, n, 0);
    }
}

int main(){
    
    int arr[] = {1,94,34,249,43};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    buildheap(arr, n);
    sortheap(arr, n);
    
    for(int x : arr){
        cout << x << " ";
    }
    
    return 0;
}

Aucun commentaire:

Enregistrer un commentaire