Binary Max Heap

/*
Tanzila Islam
CSE, Southeast University.
Dhaka-Bangladesh.
id : https://www.facebook.com/prieontypurnotamohita
mail: tanzilamohita@gmail.com
blog: http://tanzilamohita.blogspot.com/

*/




#include <iostream>

using namespace std;


class BinaryMaxHeap {

private:

    int *A;

    int length;

    int heapSize;


public:

    BinaryMaxHeap(int X[], int l) {

        A = X;

        length = l;

    }


    int left(int i) {

        return 2 * i;

    }


    int right(int i) {

        return 2 * i + 1;

    }


    int parent(int i) {

        return i / 2;

    }


    void maxHeapify(int i) {

        int l = left(i);

        int r = right(i);

        int largest;

        if (l <= heapSize && A[l] > A[i])

            largest = l;

        else largest = i;

        if (r <= heapSize && A[r] > A[largest])

            largest = r;

        if (largest != i) {

            int t = A[i];

            A[i] = A[largest];

            A[largest] = t;

            maxHeapify(largest);

        }

    }


    void buildMaxHeap() {

        heapSize = length;

        for (int i = length / 2; i >= 1; i--)

            maxHeapify(i);

    }


    void heapSort() {

        buildMaxHeap();

        for (int i = length; i >= 2; i--) {

            int t = A[i];

            A[i] = A[1];

            A[1] = t;

            heapSize = heapSize - 1;

            maxHeapify(1);

        }

    }

};


int main() {

    int X[] = {-1, 5, 12, 54, 32, 13, 67, 90, 23, 12, 36, 45, 23, 15, 56};

    int n = sizeof(X) / sizeof(X[0]) - 1;

    cout << "Before calling heapSort" << endl;

    for (int i = 1; i <= n; i++)

        cout << X[i] << " ";

    cout << endl;

    BinaryMaxHeap h(X, n);

    h.heapSort();

    cout << "After calling heapSort" << endl;

    for (int i = 1; i <= n; i++)

        cout << X[i] << " ";

    cout << endl;

    return 0;

}