在 C++ 中使用 STL 堆算法

使用 C++ STL 堆算法，可以将 std::vector 的一个范围转换为最大堆、对该范围排序，或将最大值移到末尾。std::pop_heap 只会移动该值；若要从 vector 中删除它，还需单独擦除。

使用 std::make_heap 函数将范围转换为堆

堆是一个满足父子关系规则的范围。使用默认比较方式时，std::make_heap 会创建最大堆：每个父节点都大于或等于其子节点，因此最大值位于首位。对于由 vector 表示的二叉堆，索引为 i 的元素，其子节点位于 2 * i + 1 和 2 * i + 2；只有这些位置仍在范围内时，它们才存在。最小堆则使用不同的比较方式，例如 std::greater<int>。

std::make_heap 会重新排列元素以满足堆属性，但不会对整个范围排序。多种排列都可能满足同一堆属性，因此代码应依赖首位元素以及父子节点之间的比较，而不要假定调用后元素会呈现某个特定顺序。

下面的独立示例会构建堆并检查父子节点规则。示例已成功执行，观测到的输出如下；输出标签保持英文。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    bool is_max_heap = true;
    for (std::size_t child = 1; child < values.size(); ++child) {
        const std::size_t parent = (child - 1) / 2;
        if (values[parent] < values[child]) {
            is_max_heap = false;
            break;
        }
    }

    std::cout << "max-heap: " << std::boolalpha << is_max_heap << '\n';
    std::cout << "top: " << values.front() << '\n';
}

max-heap: true
top: 91

首位元素就是堆顶。vector 中其余元素的顺序只受堆属性约束，因此不能把它们当作升序或降序列表。

使用 std::sort_heap 函数对堆范围排序

对已经满足堆属性的范围调用 std::sort_heap。使用默认比较方式时，它会将范围重新排列为升序。排序后，该范围不再满足堆属性；若要对整个范围再次执行堆操作，请先重新调用 std::make_heap。

例如，在调用 std::make_heap(values.begin(), values.end()) 后，可以调用 std::sort_heap(values.begin(), values.end()) 对同一范围排序。默认比较方式会产生升序结果。

带比较器的重载接受定义排序方式的函数或函数对象。构建和排序堆时应使用相同的比较方式；例如，使用 std::greater<int> 构建的堆，也必须使用该比较器排序。若目标是得到升序结果，默认重载即可满足需要。

使用 std::pop_heap 函数移除堆中的下一个元素

std::pop_heap 会将堆顶值移到范围的最后一个位置，并恢复前面那段范围的堆属性。它不会改变 vector 的大小。若要从容器中删除该值，请在调用 std::pop_heap 后再调用 pop_back()。

要添加元素，先将它追加到 vector，再调用 std::push_heap。追加元素之前的范围必须已经是一个堆；随后 std::push_heap 会恢复整个扩展范围的堆属性。对于这两个算法，都应使用定义该堆的同一比较器。

下面的独立示例会检查移到末尾的堆顶值，单独擦除该值，然后添加一个值并维持堆属性。示例已成功执行，观测到的输出如下。输出标签保持英文：其中显示的堆顶移出值为 91；删除该值并添加新值后，显示的新堆顶为 95。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    std::pop_heap(values.begin(), values.end());
    std::cout << "moved top: " << values.back() << '\n';
    values.pop_back();

    values.push_back(95);
    std::push_heap(values.begin(), values.end());
    std::cout << "new top: " << values.front() << '\n';
}

moved top: 91
new top: 95

调用 std::pop_heap 后，末尾元素之前的前缀就是可继续使用的堆。pop_back() 删除末尾值后，整个 vector 恰好又包含这个堆范围。如果追加元素时没有先维持这一不变量，就不满足 std::push_heap 的前置条件。