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