当前位置: 首页> 财经> 创投人物 > 【CPP】优先级队列

【CPP】优先级队列

时间:2025/7/11 0:17:13来源:https://blog.csdn.net/2302_79031646/article/details/140823818 浏览次数:0次

目录

  • 1.什么是优先级队列???
  • 2.优先级队列的基本使用与理解
  • 3.优先级队列的模拟实现

今天来简单分享一下写一个极简版的优先级队列。

1.什么是优先级队列???

在这里插入图片描述

优先级队列属于STL中队列的一种,虽然包含在队列容器里,但它并不是真正的队列。
在本质上,优先级队列更像一个堆,默认是大堆。
链接:LINK

下面我们简单来认识一下优先级队列的基本使用。

2.优先级队列的基本使用与理解

优先级队列的主要接口有下面这些:
在这里插入图片描述

// 优先级队列,默认底层是大堆。
priority_queue<int> ps;
ps.push(2);
ps.push(3);
ps.push(4);
ps.push(1);while (!ps.empty())
{cout << ps.top() << " ";ps.pop();
}

在这里插入图片描述
那可以让他变成小堆吗?当然可以。但是需要用到仿函数。

// 优先级队列,可以用仿函数置为小堆
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(2);
pq.push(3);
pq.push(4);
pq.push(1);while (!pq.empty())
{cout << pq.top() << " ";pq.pop();
}

在这里插入图片描述

这里区分两个概念:取出结果是有序与真正排序的区别。
在上面优先级队列中,我们发现while+top取出的数据是有序的,这是因为我们每次取得都是堆顶元素。至于怎么弄的,可以参考C数据结构钟堆删除数据时候得操作,首尾交换,然后size–,我觉得应该是相同的操作。
在这里插入图片描述

// 我们发现sort默认排序为升序。
vector<int> v = { 1,3,4,2 };
vector<int>::iterator it = v.begin();
while (it != v.end())
{cout << *it << " ";it++;
}
cout << endl;sort(v.begin(), v.end());
it = v.begin();
while (it != v.end())
{cout << *it << " ";it++;
}

在这里插入图片描述
为了让sort变成升序,我们也可以用仿函数进行设置。

vector<int> v = { 1,3,4,2 };
vector<int>::iterator it = v.begin();
while (it != v.end())
{cout << *it << " ";it++;
}
cout << endl;sort(v.begin(), v.end(), greater<int>());
it = v.begin();
while (it != v.end())
{cout << *it << " ";it++;
}

在这里插入图片描述

重点区分一个地方:模板参数与函数参数的需要
priority_queue<int, vector<int>, greater<int>> pq;
sort(v.begin(), v.end(), greater<int>());
我们发现两个greater一个带括号一个不带,这是什么情况呢?

要注意优先级队列是一种模板,需要的是类型进行实例化,而sort是模板实例化出来的一种函数,需要迭代器区间和具体的比较仿函数对象,而不是仅仅一个仿函数类型就行。

3.优先级队列的模拟实现

#pragma once
#include<vector>
#include<iostream>
using namespace std;template<typename T>
struct Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<typename T>
struct Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};template<class T, class Container = vector<T>, class Compare = Greater<T>>
class periority_queue
{
private:Container _con;
public:void adjust_up(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[child], _con[parent])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent){Compare com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child + 1], _con[child])){child = child + 1;}if (com(_con[child], _con[parent])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con[0];}
};

其实大部分接口实现都是复用vector的,但是插入和删除接口的逻辑还需要重点看一下。整体没什么难点,需要注意的是我们实现用了一个comper的东西去控制是建小堆/大堆。
comper传的是仿函数类型。我们在向上/向下调整算法中使用这个仿函数类型生成了仿函数(函数对象)进行控制。

引入仿函数的意义:
在本实例中,仿函数是用来控制是建大堆/小堆的,我们C语言可以传函数指针来控制,这个CPP的话比较习惯用仿函数,说白了就是传入一个特殊类对象来控制,感觉无论是C语言的传函数指针还是CPP传仿函数如果控制得当都挺好用,当然前提是C语言那个指针得玩的明白。CPP这个算是一种难度降低吧,毕竟函数指针有时候会弄错。


EOF

关键字:【CPP】优先级队列

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: