Heap Sort Algorithm in CPP

1. Introduction

Heap Sort is a comparison-based sorting algorithm that leverages the properties of a binary heap. It divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

2. Implementation Steps

1. Build a max heap from the input data.

2. The largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of the heap by one. Finally, heapify the root of the tree.

3. Repeat the above step while the size of the heap is greater than 1.

3. Implementation in C++ Programming

#include<iostream>
#include<vector>
// To heapify a subtree rooted with node i which is an index in arr[]
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;  // Initialize largest as root
    int left = 2 * i + 1;  // left child
    int right = 2 * i + 2;  // right child
    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);
    }
}
void heapSort(std::vector<int>& arr) {
    int n = arr.size();
    // Build a maxheap
    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--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    heapSort(arr);
    std::cout << "Sorted array: \n";
    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

Output:

Sorted array:
5 6 7 11 12 13

Explanation:

1. Heap Sort starts by building a max heap from the input data. This means that for any given node i, the value of i is greater than its children. This property ensures that the largest element is at the root.

2. After constructing the max heap, the root (which is the largest element) is swapped with the last element. The size of the heap is reduced by one, and the root is heapified to maintain the max heap property.

3. This process of swapping the root with the last element and reducing the heap size is repeated until all the elements are sorted. The use of the heap data structure provides an efficient way to access the largest unsorted element, making the sort operation more efficient than some other naive sorting algorithms.