当前位置：首页 > news >正文

C++奇迹之旅：快速上手Priority_queue的使用与模拟实现

news 2025/5/7 22:48:10

请添加图片描述

文章目录

📝priority_queue的介绍和使用
🌠 priority_queue的介绍
- 🌉priority_queue的使用
🌠仿函数的使用
🌠C语言有趣的模仿push_back
🌠priority_queue的模拟实现
🚩总结

📝priority_queue的介绍和使用

🌠 priority_queue的介绍

priority_queue官方文档:https://legacy.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue
在这里插入图片描述

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素（优先队列中，位于顶部的元素）
优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素，元素从特定容器的尾部弹出，其称为优先队列的顶部。
底层容器可以是任意标准容器类模版，也可以是其他特定设计的容器类。容器应该可以随机访问迭代器访问，并支持以下的操作：

empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素

标准容器类vector和deque满足这些需求。默认情况下，如果没没有为特定的priority_queue类实例化指定容器类，则使用vector.
需要支持随机访问迭代器，以便始终在内部保持堆结构，容器适配器通过在需要时自动调用算法函数make_heap,push_heap,和pop_heap来完成自动操作

🌉priority_queue的使用

优先级队列默认使用vector作为其底层容器存储数据的容器，在vector上又使用堆算法讲vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的成员位置，都可以考虑使用priority_queue。
注意：默认情况下priority_queue是大堆

数说明	接口说明
priority_queue()/priority_queue(first,last)	构造空的栈
empty()	J检测优先级队列是否为空，是返回true,否则返回false
size()	返回元素的个数
top()	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

需要注意的是：

默认情况下，priority_queue是大堆

在这里插入图片描述

在这里插入图片描述
如果需要要得到小堆，修改比较方式就好，比较方式可以有仿函数，函数指针，函数模板，类模版等等，
比如使用function文件的

正常来说，greate是用来降序，大根堆，这里跟往常使用不同，因此，需要注意！！

如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d);
private:int _year;int _month;int _day;
};ostream& operator<<(ostream& _cout, const Date& d)
{_cout << d._year << "-" << d._month << "-" << d._day;return _cout;
}struct PDateLess
{bool operator()(Date* p1, Date* p2){return *p1 < *p2;}
};void TestPriorityQueue()
{// 大堆，需要用户在自定义类型中提供<的重载bit::priority_queue<Date*, vector<Date*>, PDateLess> q1;q1.push(new Date(2018, 10, 29));q1.push(new Date(2018, 10, 28));q1.push(new Date(2018, 10, 30));while (!q1.empty()){cout << *q1.top() << " ";q1.pop();}cout << endl;
}int main()
{TestPriorityQueue();return 0;
}

如在OJ中的使用
数组中的第K个最大元素：https://leetcode.cn/problems/kth-largest-element-in-an-array/description/

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {// 将数组中的元素先放入优先级队列中priority_queue<int> p(nums.begin(), nums.end());// 将优先级队列中前k-1个元素删除掉for (int i = 0; i < k - 1; ++i){p.pop();}return p.top();}
};

🌠仿函数的使用

仿函数/函数对象:重载了operator()的类，类的对象可以像函数一样使用operator()特点，参数个数和返回值根据需求确定，不固定，很灵活

// 定义一个仿函数类
class Add {
public:// 重载 operator()，接受两个参数并返回它们的和int operator()(int a, int b) {return a + b;}
};int main() {// 创建仿函数对象Add add;// 使用仿函数int result = add(3, 4); // 调用 operator()std::cout << "3 + 4 = " << result << std::endl;return 0;
}

灵活使用：

class Func
{
public:void operator()(int n){while (n--){cout << "Func调用" << endl;}cout << endl;}
};
int main()
{//仿函数Func f1;f1(10);f1.operator()(10);return 0;
}

在这里插入图片描述

🌠C语言有趣的模仿push_back

void PushBack(int x)
{printf("void PushBack(int x)\n");
}// C
struct Vector
{void(*push_back)(int);int* _a;int _size;int _capacity;
};void Init(struct Vector* pv)
{pv->push_back = PushBack;//...
}int main()
{Vector v;Init(&v);v.push_back(1);v.push_back(2);return 0;
}

在这里插入图片描述

🌠priority_queue的模拟实现

通过对priority_queue的底层结构就是堆，因此此处只需对对进行通用的封装即可。

基本框架

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;namespace own
{template<class T>struct myless{bool operator()(const T& x, const T& y){return x < y;}};template<class T>struct mygreater{bool operator()(const T& x, const T& y){return x > y;}};template <class T,class Container = vector<T>,class Compare = myless<T>>class priority_queue{public://强制编译器生成priority_queue() = default;T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

使用迭代器添加元素数据进数组：
当数据都进vector容器，我们随带建堆：

template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{while (first != last){_con.push_back(*first);++first;}//从顶开始建堆for (size_t i = 0 ;i < _con.size();++i){adjustup(i);}
}

建堆两种方式：向上建堆：向下建堆：

//第一种
void adjustup(size_t child)
{Compare comfunc;while (child > 0){size_t parent = (child - 1) / 2;if (comfunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = child * 2 + 1;}else{break;}}
}//第二种
void adjustup(int child)
{Compare comfunc;while (child > 0){size_t parent = (child - 1) / 2;if (comfunc(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;//加不加这个parent都可以，因为上面可以再次获取,加了可以方便理解//parent = (child - 1) / 2;}else{break;}}
//}//第三种//也可以是这样的写法
void adjustup(int child)
{Compare comfunc;size_t parent = (child - 1) / 2;//                      // 注意：这里的parent 和child的顺序要和adjustdown的if (comfunc(_con[parent] , _con[child]))比较顺序一致while (comfunc(_con[parent] , _con[child])) {swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}
}

向下调整建堆：

void adjustdown(int parent)
{Compare comfunc;size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && comfunc(_con[child] , _con[child + 1])){++child;}if (comfunc(_con[parent] , _con[child]))//注意：这里的parent 和child的顺序要和adjustupwhile (comfunc(_con[parent] , _con[child]))顺序一致{swap(_con[parent], _con[child]);parent = child;child = 2 * parent + 1;}else{break;}}
}

两个操作push和pop

void push(const T& x)
{_con.push_back(x);adjustup(_con.size() - 1);
}void pop()
{std::swap(_con[0], _con[_con.size()-1]);_con.pop_back();adjustdown(0);
}

在这里插入图片描述

priority_queue的源代码：

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;namespace own
{template<class T>struct myless{bool operator()(const T& x, const T& y){return x < y;}};template<class T>struct mygreater{bool operator()(const T& x, const T& y){return x > y;}};template <class T,class Container = vector<T>,class Compare = myless<T>>class priority_queue{public://强制编译器生成priority_queue() = default;//template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first;}//从顶开始建堆for (size_t i = 0 ;i < _con.size();++i){adjustup(i);}}//void adjustup(size_t child)//{//	Compare comfunc;//	while (child > 0)//	{//		size_t parent = (child - 1) / 2;//		if (comfunc(_con[parent], _con[child]))//		{//			swap(_con[parent], _con[child]);//			child = parent;//			parent = child * 2 + 1;//		}//		else//		{//			break;//		}//	}//}//void adjustup(int child)//{//	Compare comfunc;//	while (child > 0)//	{//		size_t parent = (child - 1) / 2;//		if (comfunc(_con[parent], _con[child]))//		{//			swap(_con[child], _con[parent]);//			child = parent;//			//加不加这个parent都可以，因为上面可以再次获取,加了可以方便理解//			//parent = (child - 1) / 2;//		}//		else//		{//			break;//		}//	}//}//i 为child//也可以是这样的写法void adjustup(int child){Compare comfunc;size_t parent = (child - 1) / 2;//                      // 注意：这里的parent 和child的顺序要和adjustdown的if (comfunc(_con[parent] , _con[child]))比较顺序一致while (comfunc(_con[parent] , _con[child])) {swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}}//i为parentvoid adjustdown(int parent){Compare comfunc;size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && comfunc(_con[child] , _con[child + 1])){++child;}if (comfunc(_con[parent] , _con[child]))//注意：这里的parent 和child的顺序要和adjustupwhile (comfunc(_con[parent] , _con[child]))顺序一致{swap(_con[parent], _con[child]);parent = child;child = 2 * parent + 1;}else{break;}}}void push(const T& x){_con.push_back(x);adjustup(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size()-1]);_con.pop_back();adjustdown(0);}T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}