SGI-STL源码剖析之Heap

//first: 底层容器的起始位置 iterator
//holeIndex: 新值将被置于的位置
//topIndex: 根节点在容器中的索引
//value: 新值的值
template <class RandomAccessIterator, class Distance, class T>
void __push_heap (RandomAccessIterator first, Distance holeIndex,
    Distance topIndex, T value) {
    Distance parent = (holeIndex - 1) / 2; // 找出父节点
    while (holeIndex > topIndex && *(first + parent) < value) {
        // 当尚未到达顶端，且父节点小于新值（于是不符合 heap 的次序特性）
        // 由于以 上 使用 operator< ，可知 STL heap 是 ㆒ 种 max-heap （大者为父）。
        *(first + holeIndex) = *(first + parent); // 令洞值为父值
        holeIndex = parent; // percolate up ：调整洞号，向 上 提升至父节点。
        parent = (holeIndex - 1) / 2; // 新洞的父节点
    } // 持续至顶端，或满足 heap 的次序特性为止。
    *(first + holeIndex) = value; // 令洞值为新值，完成安插动作。
}

//first: 底层容器的起始位置 iterator
//holeIndex: 被取走的根植形成 hole 位置的索引
//len: 指定了排序的区域大小
//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; // 洞节点之右子节点
    // 注意以下的比较，仅仅是左右子节点的比较，并且以两者较大者填充 hole ，然后查找新的 hole ，直至将 hole 下放到 // 叶节点。如果在此过程中割舍点的值同时大于左右两个节点，则不满足 max_heap ，这是最后需要执行一次 //__push_heap 的原因所在，所以 __push_heap 必不可少
    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;
    }
    __push_heap (first, holeIndex, topIndex, value);
}

template <class RandomAccessIterator>
void sort_heap (RandomAccessIterator first,
    RandomAccessIterator last) {
    // 以 下 ，每执行 一 次 pop_heap() ，极值（在 STL heap 中 为极大值）即被放在尾端。
    // 扣除尾端再执行 一 次 pop_heap() ，次极值又被放在新尾端。 一 直 下 去，最后即得
    // 排序结果。
    while (last - first > 1)
        pop_heap (first, last--); // 每执行 pop_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;
    // 找出第一个需要重排的子树头部，以 parent 标示出。由于任何叶节点都不需执行
    // perlocate down ，所以有以下计算。 parent 命名不佳，名为 holeIndex 更好。
    Distance parent = (len - 2)/2;
    while (true) {
        // 重排以 parent 为首的子树。 len 是为了让 __adjust_heap() 判断操作范围
        // 再次分析一下 __adjust_heap 的作用：每次 while 循环 确保且仅仅确保 了 first 到 parent 之间的数据满足 heap 。
        //__adjust_heap 下溯的 while 循环确保了其下溯路线上的节点都大于和其共父节点的节点， //__adjust_heap 上溯的 __push_heap 确保了上述下溯路线上节点父节点大于子节点
        // 综上所诉， __adjust_heap 确保了且仅仅确保了 first 到 parent 之间的数据满足 heap 。
        __adjust_heap (first, parent, len, T(*(first + parent)));
        if (parent == 0) return;
        parent--;
        // 走完根节点，就结束。
        // （即将重排之子树的）头部向前一个节点
    }
}