//STL提供的是Max heap,使用vector作为底部容器

//push_heap算法：首先将元素放到堆所对应的数组的末端，然后从该节点开始向上调整，

//若当前结点键值比父结点大，则兑换位置，如此一直上溯，直到不需对换或直到根节点为止

template <class RandomAccessIterator>

inline void push_heap(RandomAccessIterator first, RandomAccessIterator last)

{

    //该函数被调用时，新元素已置于底部容器的最末端

    _push_heap_aux(firsst, last, distance_type(first), value_type(first));

}

template <class RandomAccessIterator ,class Distance,class T>

inline void _push_heap_aux(RandomAccessIterator first, RandomAccessIterator last, Distance*, T*)

{

    _push_heap(first, Distance((last - first) - ), Distance(), T(*(last - )));

}

template <class RandomAccessIterator, class Distance, class T>

//first是根节点的迭代器，holeIndex是当前结点下标，topIndex是根节点下标，value是要调整的元素的值

void _push_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex, T value)

{

    Distance parent = (holeIndex - );//父节点下标

    while (holeIndex > topIndex&&*(first + parent) < value)

    {

        *(first + holeIndex) = *(first + parent);

        holeIndex = parent;

        parent = (holeIndex - ) / ;

    }

    *(first + holeIndex) = value;

}

//pop_heap算法：将最下层最右边的叶节点(即底层容器中最末端元素)替换根节点，然后向下调整

//pop_heap后，最大元素只是被置放于底部容器的最尾端，尚未被取走

template <class RandomAccessIterator ,class Distance,class T>

//holeIndex初始化为0,是根节点的位置,本算法先一直向下调整到叶节点，然后可能需要向上调整

//实际上没必要，只需要当当前结点比左右孩子结点的值都大时就可以停止调整了

void _adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, T value)

{

    Distance topIndex = holeIndex;

    Distance secondChild =  * holeIndex + ;//右子结点

    while (secondChild < len)

    {

        if (*(first + secondChild) < *(first + secondChild - ))

            secondChild--;

        *(first + holeIndex) = *(first = secondChild);

        holeIndex = secondChild;

        secondChild =  * (secondChild + );

    }

    if (secondChild == len)//没有右子结点，只有左子结点

    {

        *(first + holeIndex) = *(first + secondChild - );

        holeIndex = secondChild - ;

    }

    _push_heap(first, holeIndex, topIndex, value);

}

//sort_heap算法：连续调用pop_heap即可

//排序之后，原来的heap就不再符合heap的特征了

template <class RandomAccessIterator>

void sort_heap(RandomAccessIterator first, RandomAccessIterator last)

{

    while (last - first > )

        pop_heap(first, last--);

}

//make_heap算法：从最后一个非叶节点开始，每个非叶节点都向下调整

template <class RandomAccessIterator,class T,class Distance>

void _make_heap(RandomAccessIterator first, RandomAccessIterator last, T*, Distance*)

{

    if (last - first < )

        return;

    Distance len = last - first;

    Distance parent = (len - ) / ;

    while (ture)

    {

        _adjust_heap(first, parent, len, T(*(first + parent)));

        if (parent == )

            return;

        parent--;

    }

}