Implementation of Heap Sort using CPP | Heapify Function

 Problem Statement:- Implement the Heap sort algorithm implemented in CPP demonstrating heap data structure with the modularity of programming language.

Note:- Scroll horizontally to see the full line of code.

#include <iostream>

using namespace std;

class heap {

    int n;

    int *array;

public:

    heap(int n) {

        this->n = n;

        array = new int[n];

    }

    void inputheap();

    void swap(int i, int j);

    void heapify(int size, int i);

    void heapSort();

    void printheap();

};

void heap::inputheap() {

    cout << "Enter elements: " << endl;

    for (int i = 0; i < n; i++) {

        cout << i << " : ";

        cin >> array[i];

    }

}

void heap::swap(int i, int j) {

    int temp = array[i];

    array[i] = array[j];

    array[j] = temp;

}

void heap::heapify(int size, int i) {

    int largest = i;

    int left = 2 * i + 1;

    int right = 2 * i + 2;

    if (left < size && array[largest] < array[left]) {

        largest = left;

    }

    if (right < size && array[largest] < array[right]) {

        largest = right;

    }

    if (largest != i) {

        swap(largest, i);

        heapify(size, largest);

    }

}

void heap::heapSort() {

    for (int i = n / 2 - 1; i >= 0; i--) {

        heapify(n, i);

    }

    for (int i = n - 1; i >= 0; i--) {

        swap(0, i);

        heapify(i, 0);

    }

}

void heap::printheap() {

    for (int i = 0; i < n; i++) {

        cout << array[i] << "  ";

    }

    cout << endl;

}

int main() {

    int n;

    cout << "Enter no. of elements in heap: ";

    cin >> n;

    heap k(n);

    k.inputheap();

    char cont = 'y';

    while (cont == 'y') {

        cout << "<-------Menu-------->" << endl;

        cout << "1. Print Heap" << endl;

        cout << "2. Heap Sort" << endl;

        int choice;

        cout << "Enter the choice: ";

        cin >> choice;

        switch (choice) {

        case 1:

            cout << "Heap : ";

            k.printheap();

            break;

        case 2:

            k.heapSort();

            cout << "\n Heap Sort done Successfully!!!" << endl;

            break;

        default:

            cout << "Invalid Choice!!!" << endl;

            break;

        }

        cout << "Do you want to continue? (y/n): ";

        cin >> cont;

    }

    cout << "Program Ended Successfully!!!" << endl;

    return 0;

}