Heap Sort

Heap sort is a popular comparison-based sorting algorithm that uses a binary heap data structure to sort elements efficiently. It has an average and worst-case time complexity of O(n log n), making it a good choice for sorting large datasets.

Here`s how Heap Sort works

1. Heapify: First, the input array is transformed into a binary heap (max-heap or min-heap) in a process called heapify. In a max-heap, for each node, the value of that node is greater than or equal to the values of its children. In a min-heap, it's the opposite.
2. Sorting: Once the array is transformed into a heap, the largest (in a max-heap) or the smallest (in a min-heap) element is at the root of the heap. This element is swapped with the last element in the array (the unsorted portion of the array), and the heap size is reduced by one.
3. Heapify Down: After the swap, the heap property may be violated at the root node. To restore the heap property, a process called "heapify down" is performed, where the element that was moved to the root is pushed down the heap until the heap property is satisfied again.
4. Repeat: Steps 2 and 3 are repeated until the entire array is sorted. At each step, the largest (or smallest) element from the unsorted portion is moved to its correct position in the sorted portion of the array.
5. Result: After all iterations, the input array is sorted in ascending order (for max-heap) or descending order (for min-heap).

Code

#include <iostream>
#include <vector>
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;
    int left_child = 2 * i + 1;
    int right_child = 2 * i + 2;
    if (left_child < n && arr[left_child] > arr[largest]) {
        largest = left_child;
    }
    if (right_child < n && arr[right_child] > arr[largest]) {
        largest = right_child;
    }
    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}
void heapSort(std::vector<int>& arr) {
    int n = arr.size();
    // Build a 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]);  // Swap
        heapify(arr, i, 0);
    }
}
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    std::cout << "Original array:";
    for (int num : arr) {
        std::cout << " " << num;
    }
    std::cout << std::endl;
    heapSort(arr);
    std::cout << "Sorted array:";
    for (int num : arr) {
        std::cout << " " << num;
    }
    std::cout << std::endl;
    return 0;
}

Complexity

Worst-case Time Complexity (O(n log n))

In the worst-case scenario, Heap Sort has a time complexity of O(n log n). This occurs when the input array is in reverse order, meaning that each element needs to be moved to the root of the heap and then pushed down to its correct position in the heap. In this scenario, the entire sorting process takes O(n log n) time because you have to perform these operations for each element in the array.

Average-case Time Complexity (O(n log n))

The average-case time complexity of Heap Sort is also O(n log n). This holds true for most real-world scenarios, where the input data is typically random or only partially sorted. Heap Sort's efficiency is maintained due to its balanced nature, where the tree-like structure of the heap ensures that, on average, you will need to move elements up and down the tree logarithmically.

Best-case Time Complexity (O(n log n))

Heap Sort's best-case time complexity is O(n log n), which might seem counterintuitive since other sorting algorithms like Quick Sort have better best-case performance. The reason for this is that Heap Sort's initial phase, which builds the max-heap, has a time complexity of O(n). However, the subsequent sorting phase, which involves repeatedly extracting the maximum element from the heap and restoring the heap property, still dominates the time complexity, resulting in O(n log n) even in the best-case scenario.

Space Complexity (O(1))

The space complexity of Heap Sort is O(1) in the sense that it uses a constant amount of additional memory regardless of the size of the input array. Heap Sort is an in-place sorting algorithm, which means it sorts the elements within the same array without requiring significant additional memory allocation.

The space complexity is primarily determined by the operations performed on the input array itself and does not depend on the size of the input. The primary data structure used in Heap Sort is the input array, and any temporary variables or indices used during the sorting process typically require only a constant amount of memory.

In contrast to some other sorting algorithms that may require additional data structures like extra arrays or linked lists, Heap Sort's efficient use of memory makes it suitable for sorting large datasets with limited memory availability.

In Summary, Heap Sort is a reliable sorting algorithm with a consistent time complexity of O(n log n) in all cases.