《STL源码剖析》heap

Heap堆是常用的数据结构,但STL中并没有提供Heap容器，只是提供了关于Heap操作的算法。只要支持RandomAccessIterator的容器都可以作为Heap容器。

Heap分为max heap和min heap，max heap中每次取出的结点时heap结构中值最大的结点，min heap中每次取出的结点时heap结构中值最小的结点。也就是不允许遍历节点,因此heap没有迭代器.

在STL中,heap是作为priority queue(优先队列)的助手出现的.

push_heap算法方法是层层上挪，直到正确的位置.

template 
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
    // 注意，调用该函数时候，新元素位于最后一个位置(last-1)。
    __push_heap_aux(first, last, distance_type(first), value_type(first));
}

template 
inline void __push_heap_aux(RandomAccessIterator first,
    RandomAccessIterator last, Distance*, T*) {
    __push_heap(first, Distance((last - first) - 1), Distance(0),
        T(*(last - 1)));
    // (last-first)–1代表新元素的索引，0是堆首的索引，*(last - 1)是新加入的值
}

template 
void __push_heap(RandomAccessIterator first, Distance holeIndex,
    Distance topIndex, T value) {
    Distance parent = (holeIndex - 1) / 2;    // 找出父节点
    while (holeIndex > topIndex && *(first + parent) < value) {
        // 尚未到达顶端，且父节点小于新值
        // 由于以上使用 operator<，可知 STL heap 是max-heap
        *(first + holeIndex) = *(first + parent);    
        holeIndex = parent; 
        parent = (holeIndex - 1) / 2;
    }    // 持续至顶端，或满足 heap 的次序特性为止。
    *(first + holeIndex) = value;
}

pop_heap算法 月push_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));
    // pop动作的結果为底层容器的第一個元素。因此，首先设定欲调整值为尾值，然后將首值調至 
    // 尾节点（所以以上將迭代器result设为last-1）。然后重整 [first, last-1)，
    // 使之重新成一個合格的 heap。
}

template <class RandomAccessIterator, class T, class Distance>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
    RandomAccessIterator result, T value, Distance*) {
    *result = *first; // 设定尾值为首值，于是尾值即是結果，
    // 可由调用底层容器之 pop_back() 取出尾值。
    __adjust_heap(first, Distance(0), Distance(last - first), value);
    // 以上欲重新调整 heap，逗号为 0，欲调整值为value。
}

template <class RandomAccessIterator, class Distance, class T>
void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
    Distance len, T value) {
    Distance topIndex = holeIndex;
    Distance secondChild = 2 * holeIndex + 2;    // 洞节点之右子节点
    while (secondChild < len) {
        // 比较洞节点之左右兩个子值，然后以 secondChild 代表较大子节点。
        if (*(first + secondChild) < *(first + (secondChild - 1)))
            secondChild--;
        // Percolate down：令较大大子值为洞值，再令洞号下移至较大子节点处。
        *(first + holeIndex) = *(first + secondChild);
        holeIndex = secondChild;
        // 找出新洞节点的右子节点
        secondChild = 2 * (secondChild + 1);
    }

    if (secondChild == len) { // 沒有右子节点，只有左子节点
        // Percolate down：令左子值为洞值，再令洞号下移至左子节点处。
        *(first + holeIndex) = *(first + (secondChild - 1));
        holeIndex = secondChild - 1;
    }

    // 将要调整的值填入目前的括号內。注意，此时肯定满足次序特性。
    // 下面直接改为 *(first + holeIndex) = value; 应该可以。
    __push_heap(first, holeIndex, topIndex, value);
}

sort_heap 不断将极值移动到末尾，不断pop_heap,这里的极值上面说过一般是指极大值

template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
    // 以下，每执行一次 pop_heap()，极值（在STL heap中为极大值）即被放在尾端。
    // 扣除尾端再执行一次 pop_heap()，次极值又被放在新尾端。一直下去，最后即得
    // 排序結果。
    while (last - first > 1)
        pop_heap(first, last--); 
}

make_heap

// 將 [first,last) 排列為一個 heap。
template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
    __make_heap(first, last, value_type(first), distance_type(first));
}

// 以下这组。 make_heap() 不允许指定「大小比较标准」。
template <class RandomAccessIterator, class T, class Distance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
    Distance*) {
    if (last - first < 2) return;    // 如果长度为 0 或 1，不必重新排列。
    Distance len = last - first;

    Distance parent = (len - 2) / 2;

    while (true) {
        // 重排以 parent 为首的子树。len 是为了让 __adjust_heap() 判断操作范围
        __adjust_heap(first, parent, len, T(*(first + parent)));
        if (parent == 0) return;    // 走完根节点，就结束。
        parent--;                    // （即将重排之子树的）头部向前一个节点
    }
}