第十三章：集合算法与堆操作

集合算法和堆操作，这两个东西看起来不搭边，但在实际工程里，它们经常一起出现。我最早接触集合算法是在做推荐系统的时候，那时候要处理用户兴趣标签的交集、并集，手写循环写得头皮发麻。后来发现 STL 早就给我准备好了，嗯，真香。

13.1 集合算法：set_union / set_intersection / set_difference

先说集合算法。STL 提供了四个基于有序序列的集合操作：set_union（并集）、set_intersection（交集）、set_difference（差集）和 set_symmetric_difference（对称差集）。注意，它们要求输入序列必须是已排序的。

来看一个典型的用法：

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

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    std::vector<int> v2 = {3, 4, 5, 6, 7};
    std::vector<int> result;

    // 并集
    std::set_union(v1.begin(), v1.end(),
                   v2.begin(), v2.end(),
                   std::back_inserter(result));
    // result: {1, 2, 3, 4, 5, 6, 7}

    result.clear();
    // 交集
    std::set_intersection(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(result));
    // result: {3, 4, 5}

    result.clear();
    // 差集（v1 有但 v2 没有的）
    std::set_difference(v1.begin(), v1.end(),
                        v2.begin(), v2.end(),
                        std::back_inserter(result));
    // result: {1, 2}
}

我个人习惯用 std::back_inserter 来输出结果，这样不用提前分配空间。不过如果你知道结果大概有多大，提前 reserve 一下性能会更好。

13.2 includes：判断子集关系

std::includes 用来检查一个有序序列是否包含另一个有序序列的所有元素。说白了就是判断子集关系。

std::vector<int> superset = {1, 2, 3, 4, 5, 6};
std::vector<int> subset   = {2, 4, 6};

bool result = std::includes(superset.begin(), superset.end(),
                            subset.begin(), subset.end());
// result == true

这个函数在权限校验、配置检查等场景很实用。比如检查用户是否拥有某个功能所需的所有权限，用 includes 一行搞定。

13.3 堆操作：make_heap / push_heap / pop_heap / sort_heap

堆操作是 STL 里容易被忽视但非常实用的部分。它基于最大堆（默认）实现，底层容器通常是 std::vector。

核心函数就四个：

函数	作用
make_heap	将一段区间调整为堆结构
push_heap	在堆末尾插入一个新元素后，重新调整堆
pop_heap	将堆顶元素移到末尾，并调整剩余部分为堆
sort_heap	将堆排序为升序序列

来看一个完整的例子：

std::vector<int> heap = {3, 1, 4, 1, 5, 9, 2, 6};

// 建堆
std::make_heap(heap.begin(), heap.end());
// heap: {9, 6, 4, 3, 5, 1, 2, 1}

// 插入元素
heap.push_back(7);
std::push_heap(heap.begin(), heap.end());
// heap: {9, 7, 4, 6, 5, 1, 2, 1, 3}

// 弹出最大元素
std::pop_heap(heap.begin(), heap.end());
int max_val = heap.back(); // 9
heap.pop_back();
// heap: {7, 6, 4, 3, 5, 1, 2, 1}

// 堆排序
std::sort_heap(heap.begin(), heap.end());
// heap: {1, 1, 2, 3, 4, 5, 6, 7}

13.4 实战：推荐系统交集运算

好了，理论讲完了，咱们来点实际的。假设你在做一个短视频推荐系统，需要计算用户兴趣标签和视频标签的交集，然后按交集大小排序。

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

struct Video {
    std::string id;
    std::vector<std::string> tags; // 已排序
};

// 计算两个标签集合的交集大小
int intersection_count(const std::vector<std::string>& user_tags,
                       const std::vector<std::string>& video_tags) {
    std::vector<std::string> inter;
    std::set_intersection(user_tags.begin(), user_tags.end(),
                          video_tags.begin(), video_tags.end(),
                          std::back_inserter(inter));
    return inter.size();
}

int main() {
    // 用户兴趣标签（已排序）
    std::vector<std::string> user_tags = {"篮球", "美食", "旅行", "科技", "音乐"};
    
    // 候选视频列表
    std::vector<Video> videos = {
        {"v001", {"篮球", "健身", "运动"}},
        {"v002", {"美食", "旅行", "摄影"}},
        {"v003", {"科技", "编程", "AI"}},
        {"v004", {"音乐", "舞蹈", "娱乐"}},
    };
    
    // 确保所有视频标签已排序
    for (auto& v : videos) {
        std::sort(v.tags.begin(), v.tags.end());
    }
    
    // 计算每个视频的交集大小
    std::vector<std::pair<int, std::string>> scores;
    for (const auto& v : videos) {
        int cnt = intersection_count(user_tags, v.tags);
        scores.push_back({cnt, v.id});
    }
    
    // 用堆选出 Top-2 推荐
    std::make_heap(scores.begin(), scores.end());
    for (int i = 0; i < 2 && !scores.empty(); ++i) {
        std::pop_heap(scores.begin(), scores.end());
        auto top = scores.back();
        scores.pop_back();
        std::cout << "推荐视频: " << top.second
                  << " (匹配标签数: " << top.first << ")\n";
    }
}

这个例子展示了集合算法和堆操作的组合使用。先用 set_intersection 计算匹配度，再用堆来取 Top-K。为什么不直接排序？因为当视频数量很大时，堆操作只需要 O(n log k) 的时间，而全排序是 O(n log n)。

说实话，STL 的集合算法和堆操作，单独看都不难。但把它们组合起来用，能解决很多实际问题。我在做实时推荐系统时，就靠这套组合拳，把 Top-K 推荐的性能提升了将近一倍。