std::priority_queue / 堆 与 std::sort

这两个是排序算法范畴的热门考点，放一起方便对照。

第一部分：priority_queue（优先级队列）

一、概念

std::priority_queue 是容器适配器：默认底层用 std::vector，元素按堆（heap）组织，出队总是弹出最大（默认）/最小元素。

• 头文件 <queue>
• 默认：priority_queue<T> 是大顶堆（队首最大）。
• 声明：priority_queue<T, Container=vector<T>, Compare=less<T>>
• 关键方法：push、pop、top、empty、size。
• 没有迭代器、不支持遍历（接口被限制成只能 top）。

二、底层实现：二叉堆

• 底层容器 vector + 堆算法（std::make_heap/push_heap/pop_heap/sort_heap）。
• 二叉堆逻辑上是完全二叉树，物理上用数组存：下标 i 的
  • 左孩子 2*i+1
  • 右孩子 2*i+2
  • 父亲 (i-1)/2
• 复杂度：push O(log n)（上滤 sift-up）、pop O(log n)（下滤 sift-down，先 swap 顶到底再下滤）、top O(1)、建堆 make_heap O(n)。

三、高频问答

Q1. 怎么构造小顶堆？

std::priority_queue<int, std::vector<int>, std::greater<int>> minq;  // 小顶堆

less<T> 致使队首最大（大顶堆）；greater<T> 队首最小。

Q2. 想让「前 K 小/最大」用大堆还是小堆？TopK 经典题

• 求前 K 大 → 维护大小为 K 的小顶堆（堆顶是当前第 K 大，比堆顶大的进来换掉堆顶）。
• 求前 K 小 → 维护大小为 K 的大顶堆。 本质：用堆留住「临界」的 K 个，堆顶即答案门槛。

Q3. 自定义类型（如 Task{prio,id}）如何比较？

优先级队列没有「自定义比较器」的重载版本，定制顺序只能走第三个模板参数 Compare：给仿函数（重载 ()）或给类型重载 <。

Compare 的语义（常见误区）：Compare 的语义与 std::sort 完全一致——comp(a, b) == true 表示 a 排在 b 前面（a "小于" b）。而 top() 返回的是这个序里最后一个元素（没有任何元素排在它前面）→ 所以默认 less<T> 得到大顶堆；想要小顶堆就把谓词反向。

struct Task { int prio; int id; };

// ① 仿函数：C++98 起可用，且可默认构造（能出现在模板实参里直接用）
struct TaskLess {
    bool operator()(const Task& a, const Task& b) const {
        return a.prio < b.prio;   // 大顶堆按 prio
    }
};
std::priority_queue<Task, std::vector<Task>, TaskLess> pq1;

// ② 给类型重载 operator<：priority_queue<Task> 直接可用，但这是全局顺序，
//    map/sort/其它比较都会跟着变——除非该类型的全局顺序本就该按 prio 排序，否则不建议这样做。

可以用 lambda 吗？可以，但要配 decltype + 把实例传进构造函数：

// ③ lambda + decltype：C++17 及以前闭包类型不可默认构造，实例必须传进去
auto cmp = [](const Task& a, const Task& b) { return a.prio < b.prio; };
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> pq2(cmp);

// C++20：无捕获 lambda 可默认构造，且允许出现在非求值语境 → 可以内联写
std::priority_queue<Task, std::vector<Task>,
    decltype([](const Task& a, const Task& b) { return a.prio < b.prio; })> pq3;

// 捕获型 lambda：也行，同样必须把实例传给构造函数
int bias = 0;
auto cmp2 = [bias](const Task& a, const Task& b) { return a.prio < b.prio + bias; };
std::priority_queue<Task, std::vector<Task>, decltype(cmp2)> pq4(cmp2);

易错点：

• C++17 下写了 decltype(cmp) 却不传实例 → 编译错误（no matching function for call to priority_queue()）；C++20 起同一份代码才合法。
• 用函数指针当 Compare（bool (*)(const Task&, const Task&)）是合法的，而且它是可默认构造的——默认构造出来是 nullptr；容器里只有 1 个元素时不发生比较，"看着能跑"，push 第二个元素立刻空指针调用 → SIGSEGV。要用函数指针就必须显式传进去。
• 大 / 小顶堆：a.prio < b.prio → 大顶堆；a.prio > b.prio → 小顶堆（等价 std::greater<Task>）。
• 谓词必须是严格弱序。优先级相等的元素在堆里的先后未定义；要确定性就补 tie-break：if (a.prio != b.prio) return a.prio < b.prio; return a.id < b.id;
• std::function<bool(const Task&, const Task&)> 也能当 Compare，但多一层类型擦除的间接调用、无法内联，性能敏感场景避免（这正是 C++20 允许内联 lambda 的意义）。

记忆锚点：Compare 语义与 std::sort 相同（comp(a,b) = a 更靠前），但 top() 取的是"最靠后"的那个 → 默认 less = 大顶堆；lambda 当 Compare 要 decltype + 传实例（C++17），C++20 才能内联默认构造。

Q3.1（追问）为什么 std::sort 可以直接传 lambda / 函数，priority_queue 却要写 decltype？

因为一个是函数模板，一个是类模板。

// 函数模板：Compare 是「函数参数」，类型由实参推导，调用点不需要你写出类型
template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);      // comp 是值参数，用完即弃

// 类模板：Compare 是「模板参数」，类型必须在声明点由你写出
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue;

四个连带差异：

1. 推导 vs 具名：sort(v.begin(), v.end(), [](auto& a, auto& b){…}) 里编译器从实参推出匿名闭包类型；类模板没有实参可推（C++17 前完全不能推），所以 lambda 只能塞进一个变量、用 decltype 把类型捞出来。
2. 不存储 vs 存储：sort 只在这次调用里用 comp，函数返回就丢掉 → 不要求可默认构造，捕获型 lambda 直接用也没问题。priority_queue 把 Compare 当成员存起来（之后每次 push/pop 都要用），所以构造容器时就必须构造出它。
3. 默认构造：priority_queue<T> 的默认构造函数要执行 Compare()，所以 Compare 类型得可默认构造——这正是 C++20 前「无捕获 lambda 也不行」的原因；sort 无此要求。
4. CTAD 只是打了个补丁：C++17 给 priority_queue 加了推导指引，但没有「只给 Compare」的指引，必须把容器也交出去：

auto cmp = [](const Task& a, const Task& b) { return a.prio < b.prio; };
std::priority_queue pq(cmp, std::vector<Task>{});   // ✅ CTAD：(Compare, Container)
std::priority_queue pq(cmp);                        // ❌ deduction failed（无对应 guide）

想彻底写成人运行时参数？那就自付类型擦除：std::priority_queue<Task, std::vector<Task>, std::function<bool(const Task&, const Task&)>>——lambda 隐式转换成 std::function，连默认构造都合法。代价是每次比较多一层间接调用、无法内联（comparator 每次进入 lambda 体）。注意默认构造出来的是空 std::function，一比较就抛 std::bad_function_call（退出码 134），所以必须传实例进去。

教科书为什么不这么设计：set/map/priority_queue 走的是 policy-based design——比较器类型编译期已知，才能内联展开、零开销；换成 std::function 就等于放弃这个前提。所以标准把「擦除」留给你自己选。

记忆锚点：函数模板的参数从实参推类型，类模板的参数得你写出来；sort 的 Compare 是"路过"，priority_queue 的 Compare 是"住户"（要存、要能默认构造）。

Q4. 堆 vs priority_queue vs 其它「有序容器」区别？

• 想频繁取最大/最小 O(1)+ 高频插入删除 → 堆。
• 想完整有序遍历 → map/multiset（平衡树）。
• 堆只有 top 可用，不支持查找特定元素；要改堆中任意元素需自己实现（可用「索引堆」）。

---

第二部分：std::sort

一、概念

std::sort(first, last)：对 [first,last) 随机访问迭代器范围排序（vector/deque/array/裸数组可用；list 不行，list 用成员 sort()）。

二、底层实现（libstdc++/MSVC 大同小异）

内省排序 IntroSort = 快排 + 堆排 + 插入排序 混合（侯捷《STL源码剖析》有讲）：

1. 快排为主：递归划分，区间不断缩小。
2. 深度保护：递归深度超过 ~2×log₂(n) 时，为防止快排退化到 O(n²)，改用 堆排兜底（保证最坏 O(n log n)）。
3. 小区间用插入排序：当被排序区间元素个数 ≤ 16（阈值） 时，用直接插入排序（小规模时插入排序比快排更快，且避免递归调用开销）。
4. 若初始区间本身接近有序，有的实现先做一次检查或通过「三点取中」选 pivot 减少退化概率。

注意：std::sort 不稳定（快排本质）。需要稳定的请用 std::stable_sort（归并排序，需要额外内存，O(n log n)）。

三、高频问答

Q1. std::sort 与 qsort 区别？

• std::sort：C++ 模板、泛型、可用 lambda/仿函数（比较器是函数参数，直接推类型，见第一部分 Q3.1）、通常内联展开、更快；非稳定。
• qsort：C 库函数，基于函数指针比较器（需 void* 转换、跨函数调用开销）、存在类型转换风险。

Q2. 什么时候退化为 O(n²)？

理论上最坏情况（pivot 每次选到极值）但内省排序用深度阈值+堆排避免了退化，保证 O(n log n)。插入排序 O(n)、堆排 O(n log n)、归并 O(n log n)。已知快排不稳定时的平替用 stable_sort。

Q3. 数组 vs vector 排序有差异吗？

无——只要随机访问迭代器即可。

Q4. 尾递归 / 栈溢出？

快排递归深度 O(log n)（良好 pivot），不会太深；退化场景被堆排截断。

四、手写快排（高频，含两路/三路）

// 简洁版递归快排（面试）
int partition(int a[], int l, int r) {
    int pivot = a[(l + r) / 2];       // 取中值作 pivot，一定程度抗退化
    while (l <= r) {
        while (a[l] < pivot) ++l;
        while (a[r] > pivot) --r;
        if (l <= r) std::swap(a[l++], a[r--]);
    }
    return l;                          // 返回划分点
}
void quickSort(int a[], int l, int r) {
    if (l >= r) return;
    int p = partition(a, l, r);
    quickSort(a, l, p - 1);
    quickSort(a, p, r);
}

优化（进阶答）：三点取中、三路划分（等于 pivot 放中间，处理大量重复元素）、小区间用插入排序、尾递归转循环。这接近标准库内省排序思路。

五、记忆点

• priority_queue 的 Compare 语义同 std::sort（comp(a,b) = a 更靠前），但 top() 取最靠后的那个 → 默认 less 是大顶堆，小顶堆要反向谓词（greater 或 a.prio > b.prio）。
• 自定义类型：仿函数 / 类型重载 < / lambda（decltype + 传实例；C++20 起可内联默认构造）。
• 基本升序自定义用 lambda：std::sort(v.begin(), v.end(), [](int a,int b){return a>b;}); 降序。
• 排序 std::string（字典序）、std::pair（默认 key 再 value）、结构体需给比较规则。
• 复杂度：std::sort 平均 O(n log n)；std::stable_sort 保证 O(n log n)（最好 O(n) 当近乎有序归并时）。