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

}

CodePudding user response：

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