Question

HeapSort an array with constant space complexity O(1).

Answer 1

As we know that, the heap is built inside the array to be sorted so O(1) additional space is required.

void heapSort(int arr[], int n)
{
     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);
    }
}