heap（堆结构）

heap并不归属STL容器组件，它是priority queue(允许用户以任何次序将任何元素是推入容器内，但取出时一定是从优先权最高的元素开始取)的助手。它是一种完全二叉树，由于完全二叉树的性质，可以使用array来存储所有节点，也就是说当树中某个节点位于array的i处时，其左孩子位于2i处，有孩子位于2i+1处。这种以array表示tree的方式，称为隐式表述法。

heap可分为max-heap和min-heap两种，前者每个节点的键值都大于或等于其子节点键值，后者的每个节点键值都小于或等于其子节点键值。STL提供的是max-heap。

//向堆中添加一个元素，放在队尾，然后调用push_heap调整位置
template<class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
    __push_heap_aux(first, 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) - 1), Distance(0), T(*(last - 1)));
}

template<class RandomAccessIterator, class Distance, class T>
inline void __push_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex, T value) {
    Distance parent = (holeIndex - 1) / 2;
    while(holeIndex > topIndex && *(first + parent) < value){
        *(first + holeIndex) = *(first + parent);
        holeIndex = parent;
        parent = (holeIndex - 1) / 2;
    }
    *(first + holeIndex) = value;
}

pop_heap是拿走堆的最大值，堆顶元素拿走后，取堆的最后一个元素放在堆顶，执行下溯过程

template<class RandomAccessIterator>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
    __pop_heap_aux(first, last, value_type(first));
}

template<class RandomAccessIterator, class T>
inline void __pop_heap_aux(RandomAccessIterator first, RandomAccessIterator last, T*) {
    __pop_heap(first, last - 1, last - 1, T(*(last - 1)), distance_type(first));
}

template<class RandomAccessIterator, class T, class Distance>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator result, T value, Distance*) {
    *result = *first;      //最大元素只是被置于底部容器的最尾端
    __adjust_heap(first, Distance(0), Distance(last -  first), value);
}    

template<class RandomAccessIterator, class T, class Distance>
void __adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, T value) {
    Distance topIndex = holeIndex;
    Distance secondChild = 2 * holeIndex + 2;
    while(secondChild < len){
        if(*(first + secondChild) < *(first + (secondChild - 1))){
            secondChild--;
        }
        *(first + holeIndex) = *(first + secondChild);
        holeIndex = secondIndex;
        secondChild = 2 * (secondChild + 1);
    }
    if(secondChild == len){   //必须到叶子节点
        *(first + holeIndex) = *(first + (secondChild - 1));
        holeIndex = secondChild - 1;
    }
    __push_heap(first, holeIndex, topIndex, value); 
}

sort_heap

template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
    while(last - first > 1){
        pop_heap(first, last--);
    }
}

make_heap

template<class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
    __make_heap(first, last, value_type(first), distance_type(first));
}
template<class RandomAccessIterator, class T, class Distance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*, Distance*) {
    if(last - first < 2) { return ;}
    Distance len = last - first;
    Distance parent = (len - 2) / 2;
    while(true){
        __adjust_heap(first, parent, len, T(*(first + parent)));
        if(parent == 0) return;
        parent--;
    }
}

heap的所有元素都遵循特别的排列规则，所以heap不提供遍历功能，不提供迭代器。