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;
}

// Given the array heapify the subtree with root at index.
// Flow values downwards to make it a valid heap.
// Time = 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;
        }
    }
}

// Make max heap first for last nodes and then in reverse order.
// We need not start from leaves bcz they are already max heap, 
// rather start from parent of last node i.e. parent(size - 1)
// Time = O(n) - build heap using heapify
void buildMaxHeap(vector<int> &A, int size) {
    for (int i = parentIndx(size - 1); i >= 0; i--) {
        maxHeapify(A, i, size);
    }
}

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