Heap Sort

Heap Sort

Description: Heap sort is a comparison-based sorting algorithm that uses a data structure called a binary heap. It first builds a max heap (or min heap) from the input data, and then it repeatedly extracts the maximum (or minimum) element from the heap and reconstructs the heap until the array is sorted.

How It Works

1. Build a Max Heap: Convert the array into a max heap, where the largest element is at the root.
2. Extract Maximum: Remove the root element (the maximum) and place it at the end of the array. Reduce the size of the heap by one.
3. Re-Heapify: Restore the heap property by calling a heapify function on the root.
4. Repeat: Continue extracting the maximum and re-heapifying until the heap is empty.

Time Complexity

• Worst Case: $O(n \log n)$
• Average Case: $O(n \log n)$
• Best Case: $O(n \log n)$ — heap sort performs consistently across all cases.

Space Complexity

• Space Complexity: $O(1)$ — heap sort is an in-place sorting algorithm, requiring only a constant amount of additional space.

Stability

• Stability: Heap sort is not a stable sort. Equal elements may not maintain their relative order after sorting.

Example Code

Here's a C++ implementation of heap sort:

#include <iostream>
using namespace std;

// Function to heapify a subtree rooted at index i
void heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1; // left = 2*i + 1
    int right = 2 * i + 2; // right = 2*i + 2

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // If largest is not root, swap and continue heapifying
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

// Main function to sort an array using heap sort
void heapSort(int arr[], int n) {
    // Build a max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // One by one extract elements from heap
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]); // Move current root to end
        heapify(arr, i, 0); // Heapify the reduced heap
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Explanation of the Code

1. Function Definitions:

   • heapify: Ensures the subtree rooted at index i maintains the heap property. It checks the left and right children and swaps elements as necessary.
   • heapSort: Manages the overall sorting process. It first builds the heap and then repeatedly extracts the maximum element.

2. Building the Heap:

   • The first loop in heapSort constructs the max heap by calling heapify on each non-leaf node starting from the last parent node down to the root.

3. Extracting Elements:

   • The second loop extracts the maximum element (the root of the heap) by swapping it with the last element in the array, reducing the heap size, and calling heapify to restore the heap property.

4. Output: After sorting, the program prints the sorted array.

Conclusion

Heap sort is an efficient sorting algorithm with a guaranteed $O(n \log n)$ time complexity. It uses a binary heap data structure to sort elements in place, making it suitable for large datasets. However, its lack of stability and the more complex implementation compared to simpler algorithms like quick sort and merge sort might make it less popular in certain contexts. Nevertheless, heap sort is often used in applications where memory usage is a concern, as it operates in constant space.