Lecture 328:- Let's Code Heap Sort

Here's a C++ implementation of the Heap Sort algorithm:

cppCopy code

#include <iostream> #include <vector> using namespace std; // Function to heapify (bubble-down) the element at a given index in a max heap void maxHeapify(vector<int>& arr, int index, int heapSize) {    int largest = index;    int leftChild = 2 * index + 1;    int rightChild = 2 * index + 2;    if (leftChild < heapSize && arr[leftChild] > arr[largest])        largest = leftChild;    if (rightChild < heapSize && arr[rightChild] > arr[largest])        largest = rightChild;    if (largest != index) {        swap(arr[index], arr[largest]);        maxHeapify(arr, largest, heapSize);    } } // Function to build a max heap from an input array void buildMaxHeap(vector<int>& arr) {    int n = arr.size();    for (int i = n / 2 - 1; i >= 0; i--)        maxHeapify(arr, i, n); } // Function to perform Heap Sort on an input array void heapSort(vector<int>& arr) {    int n = arr.size();    buildMaxHeap(arr);    // Heap sort: repeatedly extract the root and place it at the end    for (int i = n - 1; i > 0; i--) {        swap(arr[0], arr[i]);        maxHeapify(arr, 0, i);    } } // Function to display the elements of the array void display(const vector<int>& arr) {    for (int val : arr)        cout << val << " ";    cout << endl; } int main() {    vector<int> arr = {12, 11, 13, 5, 6, 7};    cout << "Original Array: ";    display(arr);    heapSort(arr);    cout << "Sorted Array (Ascending): ";    display(arr);    return 0; }

In this program, the maxHeapify function is used to heapify the elements in a max heap. The buildMaxHeap function builds a max heap from the input array, and the heapSort function uses the max heap to perform the sorting process. Finally, the display function is used to display the elements of the array.

When you run this C++ program, it will display the original array and then the sorted array in ascending order using the Heap Sort algorithm.