1、priority_queue 的底层是堆，标准库中 直接使用 std::make_heap, std::push_heap, std::pop_heap 来实现 priority_queue
2、std::make_heap、std::push_heap 和 std::pop_heap 这三个函数 用于 处理堆数据结构（Heap）。堆 是一种特殊的完全二叉树，通常用于 实现优先队列，最常见的是 最大堆（每个节点的值 都大于或等于其子节点的值）或 最小堆（每个节点的值都小于或等于其子节点的值）
1）std::make_heap
功能：将一个范围内的元素转化为堆结构。
原型：template <class RandomIt> void make_heap(RandomIt first, RandomIt last);
解释：这个函数将一段范围 [first, last) 内的元素重新排列，使其符合堆的性质（默认情况下 是最大堆）
#include <iostream>
#include <algorithm>
#include <vector>int main() {std::vector<int> v = {3, 1, 4, 1, 5, 9, 2};std::make_heap(v.begin(), v.end());for (int n : v) {std::cout << n << ' '; // 输出最大堆}
}2）std::push_heap
功能：将一个新元素 插入到 已经是堆的数据结构中，并调整 使其继续保持堆的性质
原型：template <class RandomIt> void push_heap(RandomIt first, RandomIt last);
解释：假设 [first, last-1) 范围已经是一个堆，push_heap 将范围内 最后一个元素（即 *(last-1)）插入到正确的位置以维持堆的性质
#include <iostream>
#include <algorithm>
#include <vector>int main() {std::vector<int> v = {3, 1, 4, 1, 5, 9};std::make_heap(v.begin(), v.end()); // 先将其变为堆v.push_back(7); // 添加新元素std::push_heap(v.begin(), v.end()); // 调整堆结构for (int n : v) {std::cout << n << ' '; // 输出调整后的堆}
}3）std::pop_heap
功能：将堆的根元素（最大元素或最小元素）移到范围的末尾，同时 调整剩余元素，使它们仍保持堆的性质。
原型：template <class RandomIt> void pop_heap(RandomIt first, RandomIt last);
解释：pop_heap 将堆的第一个元素（根元素）与最后一个元素交换，然后调整 [first, last-1) 范围内的元素，使其依然满足堆的性质。此时，last-1 指向原来的堆顶元素
#include <iostream>
#include <algorithm>
#include <vector>int main() {std::vector<int> v = {3, 1, 4, 1, 5, 9, 2};std::make_heap(v.begin(), v.end()); // 先将其变为堆std::pop_heap(v.begin(), v.end()); // 移动最大元素到末尾v.pop_back(); // 移除最大元素for (int n : v) {std::cout << n << ' '; // 输出剩余的堆}
}1、堆的插入和删除
插入操作： 插入新元素时，新元素 首先被放置在 树的最后一个位置，以保持 完全二叉树的结构。然后，该元素 会通过一个称为“上浮”（或“堆化”）的过程，与其父节点比较 并交换位置（如果在最大堆中 新元素比父节点大，或在最小堆中 新元素比父节点小）。这个过程重复进行，直到 新元素到达一个位置，它不再比父节点大（或小，取决于 是最大堆还是最小堆），或者 它已经到达了树的顶部
删除操作： 在堆中，删除操作 通常指的是删除根节点，即最大元素 或 最小元素。删除后，堆的结构性质 必须得到维护。这通常 通过 将最后一个元素移到根节点的位置来完成，接着执行“下沉”（或“堆化”）过程，该元素 会与其子节点比较 并根据需要 与较大（或较小）的子节点交换位置。这个过程持续进行，直到 该元素位于正确的位置，或者 它已经到达了树的底部
构建堆： 从无序数组 构建堆的过程 称为堆化（Heapify）。这可以通过 从 最后一个非叶子节点开始，对每个节点执行下沉操作 来完成。在数组中，给定索引为 i 的元素，其左子节点的索引为 2 * i + 1，右子节点的索引为 2 * i + 2，父节点的索引为 (i - 1) / 2
2、利用标准库堆实现
#include <iostream>
#include <vector>
#include <algorithm> // 用于 std::make_heap, std::push_heap, std::pop_heap
#include <stdexcept>
#include <sstream> // 为了使用 istringstreamtemplate <typename T, typename Container = std::vector<T>>
class PriorityQueue {Container data; // 始终保持堆的性质public:PriorityQueue() {}PriorityQueue(const Container& c) : data(c) {std::make_heap(data.begin(), data.end());}void push(const T& val) {data.push_back(val);std::push_heap(data.begin(), data.end());}void pop() {if (!data.empty()) {std::pop_heap(data.begin(), data.end());data.pop_back();}elsethrow std::runtime_error("PriorityQueue is empty. ");}T& top() {if (!data.empty()) {return data.front(); // 顶部在数据结构的最前面}elsethrow std::runtime_error("PriorityQueue is empty. ");}bool empty() const {return data.empty();}size_t size() const {return data.size();}
};int main() {// 使用 std::vector 作为底层容器PriorityQueue<int, std::vector<int>> myPriorityQueue;int N;std::cin >> N;getchar();std::string line;for (int i = 0; i < N; i++) {std::getline(std::cin, line);std::istringstream iss(line);std::string command;iss >> command;int element;if (command == "push") {iss >> element;myPriorityQueue.push(element);}if (command == "pop") {try {myPriorityQueue.pop();}catch (const std::runtime_error& e) {// 不做任何处理，无输出continue;}}if (command == "top") {try {std::cout << myPriorityQueue.top() << std::endl;}catch (const std::runtime_error& e) {std::cout << "null" << std::endl; //如果 priority_queue 为空，则输出 null}}if (command == "size") {std::cout << myPriorityQueue.size() << std::endl;}if (command == "empty") {std::cout << (myPriorityQueue.empty() ? "true" : "false") << std::endl;}}return 0;
}
3、利用自己实现堆实现
#include <iostream>
#include <vector>
#include <stdexcept> // std::runtime_error
#include <sstream> // 为了使用 istringstream
#include <utility> // std::swap 所在的头文件template <typename T, typename Container = std::vector<T>>
class MaxHeap {Container data;// 下标int parent(int i) {return (i - 1) / 2;}int leftChild(int i) {return 2 * i + 1;}int rightChild(int i) {return 2 * i + 2;}void heapify_down(int i) { // 结点不断下沉，循环不是递归while (true) {int largest = i;int left = leftChild(i);int right = rightChild(i);// 得出三者的最大值if (left < data.size() && data[left] > data[largest]) {largest = left;}if (right < data.size() && data[right] > data[largest]) {largest = right;}if (largest != i) {std::swap(data[largest], data[i]);i = largest;}else {return; // 结束了}}}void heapify_up(int i) { // 结点不断往上升，同样是循环不是递归int par = parent(i);while (par >= 0 && data[par] < data[i]) {std::swap(data[par], data[i]);i = par;par = parent(i);}}public:MaxHeap() {}MaxHeap(const Container& c) : data(c) {int size = data.size();for (int i = (size / 2) - 1; i >= 0; i--) { // 叶子结点显然不需要下沉heapify_down(i);}}// 接受迭代器的版本MaxHeap(typename Container::iterator begin, typename Container::iterator end) {data = Container(begin, end);int size = data.size();for (int i = (size / 2) - 1; i >= 0; i--) { // 叶子结点显然不需要下沉heapify_down(i);}}void push(const T &val) {data.push_back(val);heapify_up(data.size() - 1);}void pop() {if (data.size() == 0)throw std::out_of_range("Heap is empty. ");data[0] = data.back(); // 将最后一个节点换到根位置，删除最后一个结点，再下降data.pop_back();heapify_down(0);}bool isEmpty() const {return data.size() == 0;}T& top() {return data[0];}size_t size() const {return data.size();}
};template <typename T, typename Container = std::vector<T>>
class PriorityQueue {// Container data;MaxHeap<T> mh;public:PriorityQueue() {}PriorityQueue(const Container& c) : mh(c) {}void push(const T& val) {mh.push(val);}void pop() {if (!mh.isEmpty()) {mh.pop();}elsethrow std::runtime_error("PriorityQueue is empty. ");}T& top() {if (!mh.isEmpty()) {return mh.top(); // 顶部在数据结构的最前面}elsethrow std::runtime_error("PriorityQueue is empty. ");}bool empty() const {return mh.isEmpty();}size_t size() const {return mh.size();}
};int main() {// 使用 std::vector 作为底层容器PriorityQueue<int, std::vector<int>> myPriorityQueue;int N;std::cin >> N;getchar();std::string line;for (int i = 0; i < N; i++) {std::getline(std::cin, line);std::istringstream iss(line);std::string command;iss >> command;int element;if (command == "push") {iss >> element;myPriorityQueue.push(element);}if (command == "pop") {try {myPriorityQueue.pop();}catch (const std::runtime_error& e) {// 不做任何处理，无输出continue;}}if (command == "top") {try {std::cout << myPriorityQueue.top() << std::endl;}catch (const std::runtime_error& e) {std::cout << "null" << std::endl; //如果 priority_queue 为空，则输出 null}}if (command == "size") {std::cout << myPriorityQueue.size() << std::endl;}if (command == "empty") {std::cout << (myPriorityQueue.empty() ? "true" : "false") << std::endl;}}return 0;
}
1、构造堆的过程：
为什么从 (size / 2) - 1 开始：表示 从最后一个非叶子节点开始，向上依次 对每个节点进行堆调整。这是因为 叶子节点本身已经是 符合堆的结构，无需调整
2、这里 默认构造函数 怎么自己构造 Container
template <typename T, typename Container = std::vector<T>>
class PriorityQueue {Container data;public:PriorityQueue() {}
};
Container data; 会自动调用 Container 的默认构造函数
C++ 会自动调用 Container（即 std::vector）的默认构造函数 来初始化 data，因此 data 也会被默认构造为一个空容器
3、什么情况下 默认构造函数会被自动调用
1）定义类对象时（不带初始化参数）
当定义 一个类对象 并且不提供 任何初始化参数时，默认构造函数 会自动被调用。如果 没有自定义构造函数，编译器 会生成 一个默认的空构造函数
class MyClass {
public:MyClass() { std::cout << "Default constructor called!" << std::endl;}
};int main() {MyClass obj; // 默认构造函数被调用return 0;
}2）类成员是对象时
如果 一个类 包含其他类类型的成员，并且 这些成员也有默认构造函数，当包含这些成员的类的构造函数 被调用时，这些成员的默认构造函数 也会自动调用
class A {
public:A() { std::cout << "Class A's default constructor!" << std::endl;}
};class B {A a; // A 类的对象作为 B 类的成员
public:B() { std::cout << "Class B's default constructor!" << std::endl;}
};int main() {B obj; // 先调用 A 的默认构造函数，然后调用 B 的默认构造函数return 0;
}输出：
先调用 A 的默认构造函数，然后调用 B 的默认构造函数
Class A's default constructor!
Class B's default constructor!
当没有提供 默认构造函数
如果 Member 类中 没有默认构造函数，编译器 就无法自动调用 它的默认构造函数，必须显式地调用 其其他构造函数。否则，编译器会报错
#include <iostream>class Member {
public:Member(int x) { // 只有一个参数化构造函数，没有默认构造函数std::cout << "Member constructor called with value: " << x << std::endl;}
};class MyClass {Member m; // Member 类的成员
public:MyClass(int x) : m(x) { // 必须使用初始化列表调用 Member 的构造函数std::cout << "MyClass constructor called" << std::endl;}
};int main() {MyClass obj(42);return 0;
}输出：
Member constructor called with value: 42
MyClass constructor called
没有使用初始化列表（不推荐）
如果 不使用初始化列表，成员变量 仍然会先通过 它们的默认构造函数初始化，然后在构造函数体中 再对它们进行赋值操作。这种方式效率较低，因为对象 会先被默认初始化，然后被赋予新的值
#include <iostream>class Member {
public:Member(int x = 0) { // 提供默认参数std::cout << "Member constructor called with value: " << x << std::endl;}
};class MyClass {Member m; // Member 类的成员
public:MyClass(int x) {// 构造函数体内赋值，而不是使用初始化列表m = Member(x);std::cout << "MyClass constructor called" << std::endl;}
};int main() {MyClass obj(42);return 0;
}输出：
Member constructor called with value: 0 // 先调用默认构造函数
Member constructor called with value: 42 // 然后在构造函数体内赋值
MyClass constructor called
3）数组初始化时
当创建对象数组时，每个数组元素的默认构造函数 会被自动调用。如果数组中元素的类型是 自定义类，并且 没有提供初始值，那么每个元素 都会调用默认构造函数
class MyClass {
public:MyClass() {std::cout << "Default constructor called!" << std::endl;}
};int main() {MyClass arr[3]; // 创建包含 3 个元素的数组，每个元素调用默认构造函数return 0;
}输出：
Default constructor called!
Default constructor called!
Default constructor called!
4）动态分配对象时
当使用 new 操作符动态 分配一个类对象，并且 不提供构造函数的参数时，默认构造函数 会自动调用
class MyClass {
public:MyClass() { std::cout << "Default constructor called!" << std::endl;}
};int main() {MyClass* ptr = new MyClass(); // 默认构造函数调用delete ptr; // 删除动态分配的对象return 0;
}
5）继承类时
当派生类的默认构造函数 被调用时，基类的默认构造函数 也会被自动调用。如果 派生类没有显式指定 基类构造函数，编译器会自动调用 基类的默认构造函数
class Base {
public:Base() { std::cout << "Base class default constructor called!" << std::endl;}
};class Derived : public Base {
public:Derived() {std::cout << "Derived class default constructor called!" << std::endl;}
};int main() {Derived obj; // 首先调用 Base 的默认构造函数，然后调用 Derived 的默认构造函数return 0;
}总结：
创建对象时 不传递参数
动态分配对象时 不传递参数
类的成员是 对象类型时，其成员的默认构造函数 自动调用
创建对象数组时
继承关系中 派生类调用时，基类的默认构造函数 会被自动调用
4、参数是 data.begin(), data.end() 函数参数 应该怎么写
#include <iostream>
#include <vector>
#include <algorithm> // for std::for_each// 定义一个模板函数，接受两个迭代器参数
template <typename InputIt>
void printRange(InputIt begin, InputIt end) {for (InputIt it = begin; it != end; ++it) {std::cout << *it << " ";}std::cout << std::endl;
}int main() {std::vector<int> data = {1, 2, 3, 4, 5};// 调用函数，传递 data.begin() 和 data.end() 作为参数printRange(data.begin(), data.end());return 0;
}让函数 可以对容器的任意范围进行操作，适应不同类型的容器，如 std::vector、std::list、std::set 等，且不需要 具体知道容器的类型，只要 容器支持迭代器就可以
std::for_each，可以直接 利用这些算法 而不需要手动遍历迭代器
std::vector<int> data = {1, 2, 3, 4, 5};// 使用 std::for_each 打印范围内的元素
std::for_each(data.begin(), data.end(), [](int value) {std::cout << value << " ";
});可以 通过指定迭代器类型，例如只接受 std::vector<int>::iterator 或者 std::list<int>::iterator，这样函数 只允许该特定类型的迭代器 作为参数
// 限制函数只接受 std::vector<int>::iterator 迭代器
void printVectorRange(std::vector<int>::iterator begin, std::vector<int>::iterator end) {while (begin != end) {std::cout << *begin << " ";++begin;}std::cout << std::endl;
}
5、为什么报错
template <typename T, typename Container = std::vector<T>>
MaxHeap(Container::iterator begin, Container::iterator end)
由于 在模板类中 尝试直接访问 Container::iterator，但在模板参数中，Container 还不是一个具体的类型，因此 无法直接使用 Container::iterator
Container::iterator 需要通过 typename 来显式声明，因为在模板中，Container 是一个依赖类型，编译器 不能自动推导出 它包含的类型成员
改成
MaxHeap(typename Container::iterator begin, typename Container::iterator end)
6、依赖类型，编译器 不能自动推导出它包含的类型成员：
依赖类型 是指 那些依赖于模板参数的类型。因为 这些类型在模板实例化之前 是未知的
C++编译器 在第一次看到模板时，并不会 对模板进行实例化，它只是 做基本的语法检查。因此，对于依赖于模板参数的名称，编译器 可能不知道 这个名称到底是类型 还是变量。为了明确表示这些依赖类型，C++标准引入了 typename 关键字
使用 typename 来明确告诉编译器：T::value_type 是一个类型
template <typename T>
class MyContainer {
public:typename T::value_type data;
};template <typename T>
class MyContainer {
public:T::value_type data; // 错误：没有 typename，编译器不知道 T::value_type 是什么
};解析模板时的两个阶段：
实例化解析（模板实例化阶段）：当模板 被具体类型实例化时，编译器 才会知道模板参数的具体类型，并解析 依赖于模板参数的类型
7、正在一个 const 成员函数中 返回一个非常量的引用。具体来说，top() 函数被声明为 const，但它试图返回 data[0] 的引用，而 const 成员函数 保证不会修改类的任何成员。因为 试图返回 data[0] 的非常量引用（就可以被修改），而 const 函数要求返回的值也是常量的（只有引用指针需要）
T& top() const {return data[0]; // data[0] 是一个非常量引用，但函数是 const
}
当一个成员函数被声明为 const 时，它意味着 该函数承诺 不会修改类的任何成员变量（除非 被声明为 mutable）
mutable 成员变量 可以在 const 成员函数中被修改，这是 唯一的例外
class MyClass {
private:int value;mutable int accessCount; // 可以在 const 成员函数中修改public:MyClass(int v) : value(v), accessCount(0) {}// 常量成员函数，不能修改 value，但可以修改 accessCountint getValue() const {accessCount++; // 允许修改 mutable 变量return value;}int getAccessCount() const {return accessCount;}
};int main() {MyClass obj(10);obj.getValue(); // 调用 getValue 后，accessCount 会被修改obj.getValue();std::cout << "Access count: " << obj.getAccessCount() << std::endl; // 输出 2
}- 返回值为非引用或非指针的情况
如果 返回值是 值类型（如整数、浮点数 或 对象的副本），const 成员函数 并不要求 返回的值是常量的，因为返回的是 一个临时对象或拷贝，修改它 不会影响类的状态
class Example {int value;public:Example(int v) : value(v) {}// const 成员函数：可以返回一个拷贝（值类型）int getValue() const {return value; // 返回一个拷贝，不会影响对象状态}
};- 返回引用或指针的情况
如果函数返回的是 类成员的引用或指针，为了遵守 const 成员函数的约定（不修改对象状态），必须返回 常量引用 或 常量指针，这样调用者 就无法通过 返回值修改类的成员
class Example {int value;public:Example(int v) : value(v) {}// const 成员函数：返回 const 引用const int& getValue() const {return value; // 返回常量引用，调用者不能修改 value}// 非 const 成员函数：可以返回非常量引用int& getValue() {return value; // 返回非常量引用，允许修改 value}
};- 访问 const 对象的情况
当有一个 const 对象时，只能调用 const 成员函数。这意味着 只有返回常量引用 或 常量指针的函数 才可以访问
4、高频面试题
1、如何从给定的无序数组中找到第 K 大的元素？
可以利用最小堆来解决这个问题。步骤如下：
创建一个大小为 K 的最小堆：
将数组的前 K 个元素添加到最小堆中
这可以使用 heapq.heapify() 函数在 O(k) 的时间内完成
遍历数组的剩余元素：
对于每个元素，如果其值 大于 最小堆的堆顶元素（即当前最小的元素），则：
用该元素替换堆顶元素
调整最小堆 以保持堆的性质，这个操作的时间复杂度是 O(log K)
获取结果：
遍历完成后，最小堆的堆顶元素即为第 K 大的元素
时间复杂度：O(n log k)
-
最小堆中 存储了 数组中最大的 K 个元素
初始阶段：将数组的前 K 个元素放入最小堆，堆的大小为 K
遍历阶段：对于数组中剩余的元素，如果 当前元素 大于 最小堆的堆顶（即最小的那个元素），就用 当前元素替换堆顶，然后重新调整堆（相当于把最小的那个元素删除了）
通过这个过程，最小堆始终保留着 当前已知的最大的 K 个元素（重要）。因为：
保持堆的大小为 K：任何时候堆中 都只存储 K 个元素
堆的性质：在最小堆中，堆顶元素是堆中最小的 -
最小堆的堆顶是第 K 大的元素
堆中元素的关系：最小堆中的所有元素 都是数组中最大的元素之一，但堆顶是 这些元素中最小的
第 K 大的定义：第 K 大的元素 是在数组中从大到小排序后 位于第 K 位的元素
因此，最小堆的堆顶元素是 当前最大的 K 个元素中最小的那个，也就是 整个数组中第 K 大的元素
2、插入和删除操作的 时间复杂度 O(log n)
3、堆排序是 一种利用堆结构的排序方法
将无序数组 构建成 一个最大堆
重复 从堆中删除最大元素，并将其 放到数组的尾部
时间复杂度：O(n log n)
空间复杂度：O(1)（就地排序）
4、二叉堆和斐波那契堆 有什么区别
二叉堆： 插入和删除操作的时间复杂度为 O(log n)。
斐波那契堆： 插入操作和减小关键字的时间复杂度为 O(1)，删除最小元素的时间复杂度为 O(log n)，但是均摊时间复杂度
减少键值和合并操作：斐波那契堆在这些操作上具有优势，尤其适用于需要频繁执行这些操作的算法
5、解释堆排序算法 以及 它的时间复杂度
堆排序算法的步骤如下：
构建最大堆
交换堆顶元素 与 最后一个元素，然后 减少堆的大小
重新堆化 新的堆顶元素
重复 上述步骤，直至堆的大小为 1
时间复杂度：O(n log n)
6、给定一个 k 有序数组，如何在最优时间复杂度内对它进行排序
k 有序数组是指 数组中的每个元素 最多只错位 k 个位置，也就是说，元素在排序后的位置 与原始位置的距离不超过 k。针对这种特殊的数组，可以在 O(n log k) 的时间复杂度内 对其进行排序，这比一般的排序算法（如 快速排序的 O(n log n)）在 k 较小的情况下更高效
1）算法思路：
创建一个大小为 k+1 的最小堆（时间复杂度是 O(k)）：
因为元素最多错位 k 个位置，所以前 k+1 个元素 包含了 数组开头需要的最小元素
将数组的前 k+1 个元素插入最小堆中
2）遍历数组并重建排序：
从数组的第 k+2 个元素开始，逐个遍历剩余的元素
对于每个元素：
从最小堆中取出堆顶元素（当前最小的元素，时间复杂度是 O(log k)），放到结果数组中
将当前元素插入最小堆（时间复杂度也是 O(log k)）
当遍历完所有元素后，最小堆中还会剩下 k 个元素，将它们依次取出，放到结果数组中
3）总时间复杂度分析
初始化最小堆：O(k)
遍历和处理元素：
总共 n - (k+1) + k = n - 1 次 取出和插入操作
每次操作的时间复杂度为 O(log k)
总时间复杂度：O(k) + O((n - 1) * log k) ≈ O(n log k)
#include <iostream>
#include <vector>
#include <queue>using namespace std;/*** 对 k 有序数组进行排序* @param arr 原始数组* @param k 元素错位的最大距离* @return 排序后的数组*/
vector<int> sortKSortedArray(vector<int>& arr, int k) {int n = arr.size();vector<int> result;result.reserve(n); // 预留空间，提升效率// 使用优先队列（最小堆）来管理当前的 k+1 个元素priority_queue<int, vector<int>, greater<int>> minHeap;// 将前 k+1 个元素插入最小堆for (int i = 0; i <= k && i < n; ++i) {minHeap.push(arr[i]);}// 从第 k+1 个元素开始遍历数组for (int i = k + 1; i < n; ++i) {// 取出堆顶元素（最小值），放入结果数组result.push_back(minHeap.top());minHeap.pop();// 将当前元素插入堆中minHeap.push(arr[i]);}// 将剩余的元素取出并加入结果数组while (!minHeap.empty()) {result.push_back(minHeap.top());minHeap.pop();}return result;
}int main() {vector<int> arr = {2, 6, 3, 12, 56, 8};int k = 3;vector<int> sortedArr = sortKSortedArray(arr, k);cout << "排序后的数组: ";for (int num : sortedArr) {cout << num << " ";}cout << endl;return 0;
}https://kamacoder.com/ 手写简单版本STL，内容在此基础上整理补充
