Exploring Time and Space Complexities of Heap Sort

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure.

It works by first building a max heap (or min heap) from the input array and then repeatedly extracting the maximum (or minimum) element from the heap to build the sorted array.

def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # Left child
    right = 2 * i + 2  # Right child

    # Check if left child exists and is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    # Check if right child exists and is larger than root
    if right < n and arr[right] > arr[largest]:
        largest = right

    # If largest is not root, swap and heapify the affected subtree
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Move current root to end
        heapify(arr, i, 0)  # Heapify the reduced heap

    return arr

template<typename T>
void heapify(std::vector<T>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if(left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if(right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if(largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

template<typename T>
void heap_sort(std::vector<T>& arr) {
    int n = arr.size();

    // Build max heap
    for(int i = n / 2 - 1; i >= 0; --i) {
        heapify(arr, n, i);
    }

    // Extract elements one by one
    for(int i = n - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

Time complexity: O(nlogn)

In all cases, heap sort's time complexity is O(nlogn).

This is because heap sort involves two parts:

1. Extracting the maximum element (root) of the heap.
2. Repeated heapify operations to create a new heap out of the remaining elements.

Suppose we need to sort the following array in descending order:

3, 7, 5, 1, 9, 2, 8, 6, 4

First, we need to heapify the array to build the following max heap:

9, 7, 8, 6, 5, 2, 3, 1, 4

After extracting the largest element (9), the heap is rearranged, and heapify operations continue.

So, for this array of size 9, we'll need to heapify the tree eight times on top of an additional heapify to build the heap.

So, for an array of size n, we'll heapify the tree n times. As each heap operation costs O(logn), n heap operations will thus cost O(nlogn).

Since the cost of extracting the root is O(1), we can ignore it to count the total time complexity of heap sort as O(nlogn) in all cases.

Space Complexity of Heap Sort: O(1)

Heap sort is an in-place sorting algorithm, i.e., it sorts the elements within the original array without requiring any significant additional memory allocation.

The only extra variables we need are those required for the heapify process, whose number remains constant regardless of the size of the array.

Therefore, the space complexity is O(1), making heap sort memory efficient.

When to Use Heap Sort?

Heap sort is particularly useful when space efficiency is critical and in cases where a stable sorting algorithm is not required.

It is also useful when we need a sorting algorithm that performs consistently well, even for large datasets.

When to Use:

1. Memory-Constrained Environments: Heap sort does not require significant additional space beyond the input array, making it suitable for environments with limited memory.
2. When Consistency is Required: Heap sort performs with O(nlogn) time complexity in all cases.

When to Avoid:

1. When Stable Sorting is Needed: Heap sort is not a stable sorting algorithm, i.e., it may change the relative order of equal elements. If stability is important, algorithms like Merge Sort should be used.
2. Small Datasets: Other algorithms like Quick Sort or Insertion Sort might perform better for small arrays due to lower overhead.