Im trying to write some code that could sort an array using heapsort. The heap have two children right now but i want the user to be able to choose the amount of children in the heap(d in the function heapsort).
Question: How do i make the function heapsort able to recieve a number (d) from the user and sort the array with heapsort with that amount of children?
template <typename T>
void heapify(T arr[], int n, int i) {
int biggest = i;
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;
if (leftChild < n && arr[leftChild] > arr[biggest])
{
biggest = leftChild;
}
if (rightChild < n && arr[rightChild] > arr[biggest]) {
biggest = rightChild;
}
if (biggest != i) {
swap(arr[i], arr[biggest]);
heapify(arr, n, biggest);
}
}
template <typename T>
void heapsort(T arr[], int n, int d)
{
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
Just because you made it so easy:
template <typename T>
void heapify(T arr[], int n, int d, int i) {
int biggest = i;
int childrenStart = d * i + 1;
int childrenEnd = childrenStart + d;
if (childrenEnd > n) {
childrenEnd = n;
}
for (int child = childrenStart; child < childrenEnd; ++child) {
if (arr[child] > arr[biggest]) {
biggest = child;
}
}
if (biggest != i) {
swap(arr[i], arr[biggest]);
heapify(arr, n, d, biggest);
}
}
template <typename T>
void heapsort(T arr[], int n, int d)
{
if (n<=0) {
return;
}
for (int i = (n-2) / d; i >= 0; i--) {
heapify(arr, n, d, i);
}
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, d, 0);
}
}