Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It operates in two main phases: building a heap from the input data and then sorting the heap by repeatedly extracting the maximum element.

Program Structure

The following C++ program implements the Heap Sort algorithm:

#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

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

    // Check 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 implement heap sort
void heapSort(int arr[], int n) {
    // Build heap (rearrange array)
    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); // Call heapify on the reduced heap
    }
}

// Utility function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

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

    cout << "Unsorted array: ";
    printArray(arr, n);

    heapSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

Explanation of the Program

• Heapify Function: This function ensures that the subtree rooted at index i obeys the heap property. It compares the root with its children and swaps with the larger child if necessary, then recursively heapifies the affected subtree.
• heapSort Function: This is the main function that performs the heap sort. It first builds a heap from the input array and then repeatedly extracts the maximum element from the heap, reducing the heap size each time.
• printArray Function: This utility function prints the elements of the array.
• Main Function: This is the entry point of the program, where an unsorted array is defined, and the heap sort is performed. It also displays the unsorted and sorted arrays.

Conclusion

Heap Sort is an efficient sorting algorithm with a time complexity of O(n log n). It is particularly useful when the data is too large to fit into memory, as it can sort data in place.