前言

heap 并不归属于 STL 容器组件，它是个幕后英雄，扮演 priority queue 的助手。顾名思义，priority queue 允许用户以任何次序将任何元素推人容器内，但取出时一定是从优先权最高 (也就是数值最高) 的元素开始取。binary max heap 正是具有这样的特性，适合作为 priority queue的底层机制。
———— 《STL源码剖析》侯捷

本节将会分析 heap 的实现。

heap

让我们做一点分析。如果使用 list 作为 priority queue 的底层机制，元素插人操作可享常数时间。但是要找到 list 中的极值，却需要对整个 list 进行线性扫描。我们也可以改变做法，让元素插人前先经过排序这-一关，使得 list 的元素值总是由小到大 (或由大到小)，但这么一来，虽然取得极值以及元素删除操作达到最高效率，可元素的插人却只有线性表现。

虽然以 binary search tree 作为 priority queue 的底层机制，元素的插入和极值的取得就有 O(logN) 的表现。但杀鸡用牛刀，未免小题大做，一来 binary search tree 的输入需要足够的随机性，二来 binary search tree 并不容易实现。priority queue 的复杂度，最好介于 queue 和 binary search tree 之间，才算适得其所。binary heap 便是这种条件下的适当候选人。

严格意义上来讲 heap 并不是一个容器，所以他没有实现自己的迭代器，也就没有遍历操作，它只是一种算法。

根据元索排列方式，heap 可分为 max-heap 和 min-heap 两种，前者每个节点的键值 (key) 都大于或等于其子节点键值，后者的每个节点键值 (key) 都小于或等于其子节点键值。因此，max-heap 的最大值在根节点，并总是位于底层 array 或 vector 的起头处； min-heap 的最小值在根节点，亦总是位于底层 array 或 vector 的起头处。STL 供应的是 max-heap。

heap 算法

在开始介绍之前需要明确，heap 所支持的容器必须具有 RandomAccessIterator，因而 list 不能支持 heap，进而导致了 list 不能使用 stl 的 sort() 算法，因为 stl 的 sort() 也会涉及堆排序的操作，而堆排序的底层结构就是堆了。关于这部分内容，会留到介绍 stl 算法时再详细说明。

push_heap

push_heap() 默认新元素已经插入到 heap 的末尾，之后从该元素开始调整 heap，即所谓的 percolate up。具体做法为：将当前处理的节点（holeIndex）与父节点进行比较，如果键值比父节点大就交换位置，直到不需要交换或到达根节点为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*****************************************************************************************/
// push_heap
// 该函数接受两个迭代器，表示一个 heap 容器的首尾，并且新元素已经插入到底部容器的最尾端，调整 heap
/*****************************************************************************************/

/// @brief 在堆中新加入元素，执行 percolate up 操作
/// @param first      堆的首元素迭代器
/// @param holeIndex  新加入元素的索引
/// @param topIndex   堆的首元素索引
/// @param value      新加入的元素
template <class RandomIterator, class Distance, class T>
void push_heap_aux(RandomIterator first, Distance holeIndex, Distance topIndex, T value) {
    auto parent = (holeIndex - 1) / 2;
    while (holeIndex > topIndex && *(first + parent) < value) {
        // 如果不是根节点, 并且父节点的值小于新值
        // 那么就把父节点的值赋给洞节点
        *(first + holeIndex) = *(first + parent);
        // 更新洞节点的索引
        holeIndex = parent;
        // 更新父节点的索引
        parent = (holeIndex - 1) / 2;
    }
    // 最后把新值赋给洞节点
    *(first + holeIndex) = value;
}

template <class RandomIterator, class Distance>
void push_heap_d(RandomIterator first, RandomIterator last, Distance*) {
    tinystl::push_heap_aux(first, (last - first) - 1, static_cast<Distance>(0), *(last - 1));
}

template <class RandomIterator>
void push_heap(RandomIterator first, RandomIterator last) {
    // 新元素应置于底部容器的最尾端
    tinystl::push_heap_d(first, last, distance_type(first));
}

pop_heap

pop_heap() 会将最大元素（根节点）调整至堆的尾部，执行完之后再使用容器的 pop_back() 即可得到最大值。具体做法为：对头部元素执行 percolate down 过程，不断地与最大的子节点进行交换，即下放。在 STL 的实现中，做法为直接将根节点下放至叶子节点，随后再执行了一次 percolate up 过程，即调用 push_heap() 将原始尾部的值上放到合适的位置。这里最后一步绝对不能改为 *(first + holeIndex) = value，侯捷老师的书中这里有误。

但如果在下放的过程中就检查洞节点的两个子节点与原始尾部元素之间的大小关系，在尾部元素大于两个子节点时就停止下放，之后就不用执行上放的过程，这时 *(first + holeIndex) = value 是合理的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*****************************************************************************************/
// pop_heap
// 该函数接受两个迭代器，表示 heap 容器的首尾，将 heap 的根节点取出放到容器尾部，调整 heap
/*****************************************************************************************/

/// @brief 从洞节点开始调整堆，使之重新成为一个 max-heap
/// @param first      堆的首元素迭代器
/// @param holeIndex  洞节点的索引
/// @param len        堆的长度
/// @param value      洞节点的值
template <class RandomIterator, class Distance, class T>
void adjust_heap(RandomIterator first, Distance holeIndex, Distance len, T value) {
    // percolate down
    auto topIndex = holeIndex;
    auto rchild = 2 * holeIndex + 2;
    // 调整范围为 [first, first + len)
    while (rchild < len) {
        // 找到左右子节点中较大的那个
        if (*(first + rchild) < *(first + rchild - 1)) --rchild;
        // 将较大的子节点的值赋给洞节点
        *(first + holeIndex) = *(first + rchild);
        // 更新洞节点的索引
        holeIndex = rchild;
        // 更新右子节点的索引
        rchild = 2 * (rchild + 1);
    }

    // 此时右子节点中已经是换下来的根节点值，无需调整，所以只需考虑左子节点
    if (rchild == len) {
        // 将左子节点的值赋给洞节点
        *(first + holeIndex) = *(first + rchild - 1);
        // 更新洞节点的索引为左子节点的索引
        holeIndex = rchild - 1;
    }

    // 注意：上述的下放过程并没有考虑洞节点的值是否已经大于两个子节点，而是直接下放到叶子节点
    // 所以这里需要再次进行 percolate up 操作，将洞节点的值上放到合适的位置
    // 侯捷老师的《STL源码剖析》中这部分说的是将这一步直接改为
    // *(first + holeIndex) = value;  // 这样肯定是有问题的。
    tinystl::push_heap_aux(first, holeIndex, topIndex, value);
}

template <class RandomIterator, class T, class Distance>
void pop_heap_aux(RandomIterator first, RandomIterator last, RandomIterator result, T value, Distance*) {
    // 先将首值调至尾节点，然后调整[first, last - 1)使之重新成为一个 max-heap
    *result = *first;
    tinystl::adjust_heap(first, static_cast<Distance>(0), last - first, value);
}

template <class RandomIterator>
void pop_heap(RandomIterator first, RandomIterator last) {
    // 这里之所以将 last - 1 传入，是因为 pop_heap 之后，尾部的元素就是最大的元素，只需调整 [first, last - 1)
    tinystl::pop_heap_aux(first, last - 1, last - 1, *(last - 1), distance_type(first));
}

验证

我们将最后一句改为 *(first + holeIndex) = value;，与 std 进行对比，可以很清楚地看到这样做是绝对错误的。如果条件不判断与两个子节点的大小关系，就必须执行 push_heap 才能确保正确性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void test1() {
    tinystl::vector<int> a{3, 2, 1};
    tinystl::make_heap(a.begin(), a.end());

    for (auto i : a) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

void test2() {
    std::vector<int> a{3, 2, 1};
    std::make_heap(a.begin(), a.end());

    for (auto i : a) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

int main() {
    test1();
    test2();
}

// 2 3 1 
// 3 2 1

sort_heap

既然每次 pop_heap() 可获得 heap 中键值最大的元素，如果持续对整个 heap 做 pop_heap 操作，每次将操作范围从后向前缩减一个元素 (因为 pop_heap 会把键值最大的元素放在底部容器的最尾端)，当整个程序执行完毕时，我们便有了一个递增序列。

需要注意的是，排序过后，原来的 heap 就不再是一个合法的 heap 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*****************************************************************************************/
// sort_heap
// 该函数接受两个迭代器，表示 heap 容器的首尾，不断执行 pop_heap 操作，直到首尾最多相差1
/*****************************************************************************************/

/// @brief 堆排序，每次将堆顶元素放到尾部，然后调整堆
/// @param first  堆的首元素迭代器
/// @param last   堆的尾元素迭代器
template <class RandomIterator>
void sort_heap(RandomIterator first, RandomIterator last) {
    // 从尾部开始，每次 pop_heap 之后，尾部的元素就是最大的元素
    while (last - first > 1) {
        tinystl::pop_heap(first, last--);
    }
}

make_heap

make_heap() 用于将一段现有的数据转化为一个 heap，具体做法为：从第一个非叶子节点开始，逐个执行 adjust_heap() 程序，即调整堆，在调整到首个元素时即形成了一个合法的 heap。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*****************************************************************************************/
// make_heap
// 该函数接受两个迭代器，表示 heap 容器的首尾，把容器内的数据变为一个 heap
/*****************************************************************************************/

template <class RandomIterator, class Distance>
void make_heap_aux(RandomIterator first, RandomIterator last, Distance*) {
    if (last - first < 2) return;
    auto len = last - first;
    // 由于任何一个叶节点都可以看作只包含一个元素的堆，无需调整，所以从最后一个非叶节点开始调整
    auto holeIndex = (len - 2) / 2;
    while (true) {
        // 重排以 holeIndex 为首的子树
        tinystl::adjust_heap(first, holeIndex, len, *(first + holeIndex));
        if (holeIndex == 0) return;
        holeIndex--;
    }
}

总结

heap 并不归属于 STL 容器组件，它是个幕后英雄，扮演 priority queue 的助手。heap没有自己的迭代器，只要支持 RandomAccessIterator 的容器都可以作为 Heap 容器。heap最重要的函数还是 pop 和push 的实现。下一节将会看到 priority queue 是如何利用 heap 实现的。