C++ 面试八股

Appearance

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. 怎么构造小顶堆？ ​

cpp
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 重载 () 或类型重载 <），因为 priority_queue 没有自定义比较器版本是靠第三个模板参数：

cpp
struct Task { int prio; int id; };
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> pq;

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/仿函数、通常内联展开、更快；非稳定。
  • 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），不会太深；退化场景被堆排截断。

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

cpp
// 简洁版递归快排（面试）
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 放中间，处理大量重复元素）、小区间用插入排序、尾递归转循环。这接近标准库内省排序思路。

五、记忆点 ​

  • 基本升序自定义用 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) 当近乎有序归并时）。

C++ 面试八股 · VitePress 版

整理自 xiaolincoding / cppguide