#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <iterator>
using namespace std;

template<class T> void heapify_array(vector<T>& u);
template<class T> void _top_heapify(int p, vector<T>& u, int u_size);
template<class T> void _buttom_heapify(int p, vector<T>& u, int u_size);
template<class T> void heap_sort(vector<T>& u);

template<class T> void heap_sort(vector<T>& u){
	heapify_array(u);
	for(unsigned int i=0;i<u.size();i++){
		swap(u[0], u[u.size()-1-i]);
		_top_heapify(0, u, u.size()-1-i);
	}	
}

template<class T>
void heapify_array(vector<T>& u){
    for(int i=u.size()/2; i>=0; i--){
        _top_heapify(i, u, u.size());
    }
}

template<class T>
void _top_heapify(int p, vector<T>& u, int u_size){
    int child_max_index=0;
    
	while(p<u_size/2){
		if((p+1)*2-1>u_size-1)  break;
        else if((p+1)*2-1 == u_size-1) child_max_index= u_size-1;
        else child_max_index = (u[(p+1)*2]>u[(p+1)*2-1])? (p+1)*2: (p+1)*2-1;
        
        if(u[p]<u[child_max_index]){
        	swap(u[p], u[child_max_index]);
        	p=child_max_index;
        }
        else break;
    }
}

template<class T>
void _buttom_heapify(int p, vector<T>& u, int u_size){
    while(p>0){
    	int paraent_index=0;
    	paraent_index = (p+1)/2-1;
    	
    	if(u[p]>u[paraent_index]){
    		swap(u[p], u[paraent_index]);
    		p = paraent_index;
    	}
    	else   break;
    }
}

int main(){
    vector<int> u(16, 0);
    for(unsigned int i=0; i<u.size(); i++) u[i] = rand()%u.size();
    copy(u.begin(), u.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    
    heap_sort(u);
    copy(u.begin(), u.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

}