c++algorithmheapsort

Heapsort with a selectable amount of children


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

}

Solution

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