#ifndef HEAP_HPP_
#define HEAP_HPP_

#include <algorithm>

//RAI = RandomAccessIterator
template<class RAI> void heap_sort(RAI begin, RAI end);
template<class RAI> void heapify_array(RAI begin, RAI end);
template<class RAI> void _top_heapify(RAI iter, RAI begin, RAI end);
template<class RAI> void _buttom_heapify(RAI iter, RAI begin, RAI end);

//RAI = RandomAccessIterator, BinaryOp = BinaryOpeatrion
template<class RAI, class BinaryOp> void heap_sort(RAI begin, RAI end, BinaryOp op);
template<class RAI, class BinaryOp> void heapify_array(RAI begin, RAI end, BinaryOp op);
template<class RAI, class BinaryOp> void _top_heapify(RAI iter, RAI begin, RAI end, BinaryOp op);
template<class RAI, class BinaryOp> void _buttom_heapify(RAI iter, RAI begin, RAI end, BinaryOp op);


template<class RAI>
void heap_sort(RAI begin, RAI end){
    heapify_array(begin, end);
    int size= (end-begin);
    for(RAI iter=end-1; size>0; --iter, --size){
        std::swap(*begin, *iter);
        _top_heapify(begin, begin, iter-1);
    }
}

template<class RAI, class BinaryOp>
void heap_sort(RAI begin, RAI end, BinaryOp op){
    heapify_array(begin, end, op);
    int size= (end-begin);
    for(RAI iter=end-1; size>0; --iter, --size){
        std::swap(*begin, *iter);
        _top_heapify(begin, begin, iter-1, op);
    }
}

template<class RAI>  // RAI = RandomAccessIterator
void heapify_array(RAI begin, RAI end){
    int size= (end- begin+1)/2;
    for(RAI iter=begin + size; size>=0; --iter, --size){
        _top_heapify(iter, begin, end-1);
    }
}

template<class RAI, class BinaryOp>  // RAI = RandomAccessIterator
void heapify_array(RAI begin, RAI end, BinaryOp op){
    int size= (end-begin)/2;
    for(RAI iter=begin + size; size>=0; --iter, --size){
        _top_heapify(iter, begin, end-1, op);
    }
}

template<class RAI> // RAI = RandomAccessIterator
void _top_heapify(RAI iter, RAI begin, RAI end){
    std::size_t size = end - begin +1;
    
    RAI child_max_iter;
    std::size_t child_index;
    while(iter-begin<size/2){
        child_index = (iter-begin)*2+1;

        if(child_index>=size)   break;
        else if(child_index==size-1)   child_max_iter = begin + child_index;
        else child_max_iter = (*(begin+child_index)> *(begin+child_index+1))? begin+child_index: begin+child_index+1;

        if(*iter<*child_max_iter){
            std::swap(*iter, *child_max_iter);
            iter = child_max_iter;
        }
        else break;
    }
}

template<class RAI, class BinaryOp> // RAI = RandomAccessIterator, BinaryOp = Binary Operattion
void _top_heapify(RAI iter, RAI begin, RAI end, BinaryOp op){
    std::size_t size = end - begin +1;
    
    RAI child_max_iter;
    std::size_t child_index;
    while(iter-begin<size/2){
        child_index = (iter-begin)*2+1;

        if(child_index>=size)   break;
        else if(child_index==size-1)   child_max_iter = begin + child_index;
        else child_max_iter = (op(*(begin+child_index), *(begin+child_index+1)))? begin+child_index: begin+child_index+1;

        if(!op(*iter, *child_max_iter)){
            std::swap(*iter, *child_max_iter);
            iter = child_max_iter;
        }
        else break;
    }
}

template<class RAI> // RAI = RandomAccessIterator
void _buttom_heapify(RAI iter, RAI begin, RAI end){
    std::size_t size = (end-begin) + 1;
    
    RAI paraent_iter;
    while(iter-begin>0){
        paraent_iter = begin + (((iter-begin)-1)/2);
        if(*iter>*paraent_iter){
            std::swap(*iter, *paraent_iter);
            iter = paraent_iter;
        }
        else break;     
    }
}

template<class RAI, class BinaryOp> // RAI = RandomAccessIterator, BinaryOp = Binary Operattion
void _buttom_heapify(RAI iter, RAI begin, RAI end, BinaryOp op){
    std::size_t size = (end-begin) + 1;
    
    RAI paraent_iter;
    while(iter-begin>0){
        paraent_iter = begin + (((iter-begin)-1)/2);
        if(op(*iter,*paraent_iter)){
            std::swap(*iter, *paraent_iter);
            iter = paraent_iter;
        }
        else break;     
    }
}

#endif /*HEAP_HPP_*/