#include <stdio.h>
#include <vector>
using namespace std;
 
template<class T>
void MaxHeapify(size_t parent_node, vector<T> & v)
{
    size_t left_child  = parent_node * 2 + 1;
    size_t right_child = parent_node * 2 + 2;
    size_t swap_index = parent_node;
 
    if(right_child < v.size())
    {
        if(v[left_child] > v[right_child])
        {
            if(v[parent_node] < v[left_child])
            {
                swap_index = left_child;
            }
        }
        else
        {
            if(v[parent_node] < v[right_child])
            {
                swap_index = right_child;  
            } 
        }
    }
    else if(left_child < v.size())
    {
        if(v[parent_node] < v[left_child])
        {
            swap_index = left_child;
        }
    }
 
    if(swap_index != parent_node)
    {
        swap(v[parent_node], v[swap_index]);
        MaxHeapify(swap_index, v);
    }
}
 
template<class T>
void BuildMaxHeap(vector<T> & v)
{
    for(int i = v.size()/2; i >= 0; --i)
    {
        MaxHeapify<T>(i, v);
    }
}
 
int main()
{  
    int numbers[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    vector<int> v(numbers, numbers + 9);
 
    BuildMaxHeap<int>(v);
 
    for(int i = 0; i < v.size(); ++i)
    {
        printf("%d ", v[i]);
    }
 
    return 0;
}