Untitled

#include <bits/stdc++.h> 
using namespace std;

int lChildIndx(int i) {
    return 2*i + 1;
}

int rChildIndx(int i) {
    return 2*i + 2;
}

int parentIndx(int i) {
    return (i-1)/2;
}

// O(log n)
void maxHeapify(vector<int> &A, int indx, int size) {
    while (indx < size) {
        int lIndx = lChildIndx(indx);
        int rIndx = rChildIndx(indx);
        int largestIndx;
        
        if (lIndx < size && A[lIndx] > A[indx])
            largestIndx = lIndx;
        else largestIndx = indx;
        
        if (rIndx < size && A[rIndx] > A[largestIndx])
            largestIndx = rIndx;
            
        if (largestIndx != indx) {
            swap(A[indx], A[largestIndx]);
            indx = largestIndx;
        } else {
            break;
        }
    }
}

void buildMaxHeap(vector<int> &A, int size) {
    for (int i = parentIndx(size - 1); i >= 0; i--) {
        maxHeapify(A, i, size);
    }
}

// O(nlog n)
void heapSort(vector<int> &A) {
    buildMaxHeap(A, A.size()); // O(n) time
    int size = A.size();
    for (int i = size - 1; i > 0; i--) {
        swap(A[0], A[size - 1]);
        size--;
        maxHeapify(A, 0, size); // O(log n) time. This is called n-1 time. So total = O(nlog n)
    }
    
}

int main() {
	vector<int> A = {6,9,4,15,7,2,11,10,13};
	heapSort(A);
	
	cout << "A : ";
	for (auto ele : A)
	    cout << ele << ", ";
	    
	return 0;
}