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

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

void insert(vector<int> &A, int val) {
    A.push_back(val);
    int i = A.size() - 1;
    // Flow value upwards till it forms valid max heap with its parent.
    while (A[i] > A[parentIndx(i)]) {
        swap(A[i], A[parentIndx(i)]);
        i = parentIndx(i);
    }
}

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 << ", ";
	    
	insert(A, 14);
	
	cout << endl << "After inserting 14 into A : ";
	for (auto ele : A)
	    cout << ele << ", ";
	    
	return 0;
}