文章目录
一、priority_queueu的使用
1.priority_queue的介绍
优先队列是一种容器适配器，默认情况下STL（头文件是<queue>）中使用vector作为其底层的数据结构，也就是本质上priority_queue就是vector，然后再vector的基础上添加一些算法并将其封装成接口对外暴露。而其中的算法是调整堆的算法，所以在C++中priority_queue就是堆，而且默认情况下是大根堆。
2.priority_queue的定义
①定义大根堆
priority_queue<int> heap; // 默认就是大根堆
priority_quueue<int, vector<int>, less<int>> heap;
②定义小根堆
priority_queue<int, vector<int>, greater<int>> heap;
3.priority_queue的常用接口
测试代码：
#include <queue>
using namespace std;
int main()
{
priority_queue<int> heap;
heap.push(1);
heap.push(2);
heap.push(3);
heap.push(4);
while (!heap.empty()) {
cout << heap.top() << ' '; // 将堆中的所有元素弹出
heap.pop();
}
return 0;
}
二、priority_queue的模拟实现
既然priority_queue是堆，所以我们要模拟实现priority_queue就一定了解调整堆的算法，而其中最最重要的两个算法就是：将元素插入堆时使用的向上调整法shiftUp()和删除堆顶元素的向下调整算法shiftDown()。
调整堆算法-shiftUp()-shiftDown()
shiftUp()算法
图示
代码实现：
// 大根堆的向上调整算法
void shiftUp(vector<int>& arr, int child) {
while (child > 0) {
int parent = (child - 1) / 2;
if (arr[parent] < arr[child]) {
swap(arr[parent], arr[child]);
} else {
break;
}
child = parent;
}
}
shiftDown()算法
图示：
代码实现：
// 大根堆的向下调整算法
void shiftDown(vector<int>& arr, int parent) {
while (parent * 2 + 1 < arr.size()) {
int child = parent * 2 + 1;
if (child + 1 < arr.size() && arr[child] < arr[child + 1])
child ++;
if (arr[child] > arr[parent]) {
swap(arr[child], arr[parent]);
parent = child;
} else {
break;
}
}
}
仿函数
在使用priority_queue的时候，模板的第一个参数是容器中元素的类型，第二个参数是容器适配器底层封装的数据结构，第三个参数是仿函数。
**仿函数就是行为类似于函数的对象，所谓函数行为就是“可以使用小括号传递参数，并调用对象中重载的operator()成员函数。**所以说仿函数的本质就是一个对象，并且对象中的operator()被特殊地处理过了，我们可以在operator（）中写原本我们想要在函数内部实现的内容。
那为什么要写一个类并重载它的operator()，而不是直接写一个函数去调用呢？
在一般情况下，我们如果直接调用函数，肯定是编写一个函数比较方便。因为如果想要使用仿函数一定需要写一个类，然后定义一个对象才可以使用。
举个例子：
struct Add { // 不方便
int operator() (int a, int b) {
return a + b;
}
};
int add(int a, int b) { // 方便
return a + b;
}
int main() {
Add add1;
cout << add1(1, 2) << endl; // 调用仿函数
cout << add(1, 2) << endl; // 调用函数
return 0;
}
但是如果我们想要传递一个函数到另一个函数中，这是我们不得不使用函数指针，然后利用函数指针在另一个函数中调用这个函数。但是不得不说函数指针不好记，而且不好用。这时就体现出了仿函数的优点：我们如果想要使用相同的功能，只需要传递一个对象，然后在另一个函数中只需要对象名(参数)就可以调用仿函数了，这样就方便了不少。
举个例子：
struct Add {
int operator() (int a, int b) {
return a + b;
}
};
int addFunc(int a, int b) {
return a + b;
}
// 在func函数中调用仿函数实现a + b
int func(int a, int b, Add& add) {
return add(a, b);
}
// 在func函数中使用函数指针调用addFunc实现a + b
int func(int a, int b, int(*add)(int, int)) {
return add(a, b);
}
int main() {
Add add;
cout << func(1, 2, add); // 传递类对象调用仿函数函数
cout << func(1, 2, addFunc); // 传递函数调用函数
return 0;
}
模拟实现
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
namespace zhy
{
// less和greater仿函数
template<class T>
struct less {
bool operator() (const T& left, const T& right) {
return left < right;
}
};
template<class T>
struct greater {
bool operator() (const T& left, const T& right) {
return left > right;
}
};
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue {
public:
priority_queue() {}
// 利用迭代器范围初始化建堆
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last) {
while (first != last) {
container.push_back(*first);
first ++;
}
buildHeap(container);
}
// 判空
bool empty() const {
return container.empty();
}
// 堆中元素个数
int size() const {
return container.size();
}
// 堆顶元素
const T& top() const {
return container.front();
}
// 向堆中插入元素
void push(const T& val) {
// 向上调整法
container.push_back(val);
shiftUp(container, size() - 1);
}
// 弹出堆顶元素
void pop() {
// 向下调整法
swap(container[0], container.back());
container.pop_back();
shiftDown(container, 0);
}
private:
Container container;
Compare compare;
private:
// 插入元素使用向上调整法
void shiftUp(Container& con, int child) {
while (child > 0)
{
int parent = (child - 1) >> 1;
// 使用仿函数比较
if (compare(con[parent], con[child])) {
swap(con[parent], con[child]);
} else {
break;
}
child = parent;
}
}
// 删除元素使用向下调整法
void shiftDown(Container& con, int parent) {
while (parent * 2 + 1 < size()) {
int child = parent * 2 + 1;
// 使用仿函数比较
if (child + 1 < size() && compare(con[child], con[child + 1]))
child ++;
// 使用仿函数比较
if (compare(con[parent], con[child])) {
swap(con[child], con[parent]);
parent = child;
} else {
break;
}
}
}
// 建堆
void buildHeap(Container& con) {
int pos = (size() - 2) / 2;
while (pos >= 0) {
shiftDown(con, pos);
pos --;
}
}
};
} // namespace zhy