【STL】priority_queue的使用及模拟实现

这篇具有很好参考价值的文章主要介绍了【STL】priority_queue的使用及模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言

priority_queue的使用

功能解析

基本接口

写点题目

模拟实现

结构解析

插入删除

调整函数结合仿函数

仿函数介绍

结合使用

其他功能

接口补齐

迭代器区间构造


前言

🍾打开 queue 头文件后,我们发现除了我们之前介绍过的普通队列以外,还有一个 priority_queue

【STL】priority_queue的使用及模拟实现

🍾其又名为优先级队列,之所以叫这个名字正是因为这个队列出队时会根据某种优先级弹出元素

🍾听到这个功能是不是觉得有点耳熟,这不就跟我们以前写过的堆一模一样吗?实际上便可以将其当作是库中封装的堆,同时配合模板使其具有更多的自由度。


priority_queue的使用

功能解析

在使用 priority_queue 之前,我们先看一下文档中的内容,模板中有三个参数,分别是内置数据类型内置容器仿函数

【STL】priority_queue的使用及模拟实现

🍾后面两个参数默认有缺省值,直接使用缺省值便是使用 vector 适配构建一个大堆

[注意] 这里的内置容器可以使用vector和deque,不能使用list。

int main()
{
	priority_queue<int> pq1;    //内部数据类型为int,数据类型为vector,构建大堆
	priority_queue<int, deque<int>> pq2; //内部数据类型为int,数据类型为deque,构建大堆
	priority_queue<int, vector<int>, greater<int>> pq3; //内部数据类型为int,数据类型为vector,构建小堆
	return 0;
}

基本接口

【STL】priority_queue的使用及模拟实现

🍾接口的命名方式与 stack 和 queue 接近,访问第一个元素是 top 而不是 front 不要和 queue 记混了。

🍾下面通过实例代码简单使用一下:

int main()
{
	priority_queue<int> pq;    //内部数据类型为int,数据类型为vector,构建大堆
	pq.push(1);    //插入数据
	pq.push(0);
	pq.push(5);
	pq.push(2);
	pq.push(1);
	pq.push(7);

	while (!pq.empty())   //直到堆为空之前循环
	{
		cout << pq.top() << " ";  //打印堆顶
		pq.pop();     //弹出元素
	}
	return 0;
}

🍾之后就是根据从大到小的顺序进行输出。 

 【STL】priority_queue的使用及模拟实现

🍾现在我们使用迭代器区间构造小堆,最后输出的结果便是从小到大的。

int main()
{
	int a[] = { 5,4,8,2,5,7,3,9 };
	priority_queue<int, vector<int>, greater<int>> pq(a, a + 8); //使用迭代器区间构造

	while (!pq.empty())   //直到堆为空之前循环
	{
		cout << pq.top() << " ";  //打印堆顶
		pq.pop();     //弹出元素
	}
	return 0;
}

【STL】priority_queue的使用及模拟实现

写点题目

🍾又得将我们 Kvalue 这个题目拎出来了,以前写的时候我们还要自己手搓一个堆出来,今非昔比,我们可以直接使用库里的堆了。

【STL】priority_queue的使用及模拟实现

🍾要求出第大 k 的值,那我们不妨维护一个 k 个值的堆让数组之后的每一个值都与堆顶元素进行对比,只有比堆顶元素大的元素才插入。同时,为了维护这个效果堆顶元素必须使整个堆中最小的那个元素,因此构建小堆。遍历完整个数组后,堆顶元素就是我们要求的目标值。

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq(nums.begin(),nums.begin()+k);   //以数组前k个值构建小堆
    for (int i = k; i < nums.size(); i++)   //遍历数组
    {
        int t = pq.top();  
        if(nums[i]>t)      //比堆顶元素大先删除原堆顶元素,再插入
        {
            pq.pop();
            pq.push(nums[i]);
        }
    }
    return pq.top();
}

模拟实现

🍾priority_queue 的模拟实现本质上就是借助仿函数和模板对堆进行封装,与之前的讲解侧重点可能不同。

🍾更多细节可以去这里复习一下,堆及堆排序的实现。

结构解析

🍾根据模板参数定义内置容器和仿函数的对象,而仿函数在下面会进行讲解。

namespace Alpaca
{
    template<class T,class Container = vector<T>,class Compare = less<T>>
	class priority_queue
	{
	public:
    private:
		Container _con;     //内置容器
		Compare com;        //仿函数
	};
}

插入删除

🍾在之前实现堆的时候,插入和删除的操作都是在数组尾部进行的

🍾插入时就直接插入到数组尾,之后再向上调整,而删除需要将堆顶的数据交换到数组尾部,再进行删除,同时,交换上去的那个数需要进行向下调整

void push(const T& x)
{
	_con.push_back(x);
	adjust_up(_con.size()-1);
}

void pop()
{
	std::swap(_con[0], _con.back());
	_con.pop_back();
	adjust_down(0);
}

调整函数结合仿函数

仿函数介绍

🍾在讲这部分之前先简单介绍一下仿函数,我们在一个类中只进行 ( ) 运算符重载,这之后我们便可以像使用函数一样使用这个类。

🍾如下,我实现一个仿函数用于判断两个值的大小。

struct judge     //直接使用struct定义类使成员函数默认为共有访问的
{
	bool operator ()(const int x, const int y)
	{
		return x > y;
	}
};

int main()
{
	int a = 8, b = 7;
	judge jud;                      //实例化对象
	cout << jud(a, b) << endl;
	cout << judge()(a, b) << endl;  //使用匿名对象
	return 0;
}

🍾实际上便于函数指针相像,但使用起来会相较函数指针更加简单一些。

🍾之前我们写堆的时候一次只能写一份构建的大堆小堆也是写死的,使用了仿函数后便可以将生成的选项交给使用者选择。

🍾将调整函数与仿函数结合起来就是接下来我们关注的重点。

结合使用

🍾一个值在数组尾插入后需要根据优先级在堆中找到其对应的位置,因此要进行向上调整,但在以前构建大堆还是小堆是我们在写的时候直接写死的,这里我们就要结合仿函数进行实现。于是在判断时我们便可直接沿用仿函数的返回值,而仿函数的选择由用户决定

🍾这样便可由用户自主决定构建出来的是大堆还是小堆,高自由度的同时还能够支持自定义类型的比较(仿函数也可以由用户构建)。

template<class T>    //沿用了库中仿函数的命名规则
struct greater
{
	bool operator ()(const T& x, const T& y)
	{
    	return x > y;
	}
};

template<class T>
struct less
{
	bool operator ()(const T& x, const T& y)
	{
		return x < y;
	}
};

🍾自己实现仿函数后便可以将其带入到调整函数中去了,同时由于我们在成员变量中定义对象了,因此这里直接使用即可。

void adjust_up(int child)
{
	int parent = (child - 1) / 2;               //向上找父亲
	while (child > 0)
	{
		if (com(_con[parent], _con[child]))     //判断是否符合优先级
		{
			std::swap(_con[child], _con[parent]);   //符合就向上调整,否则结束调整
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void adjust_down(int parent)
{
	int child = parent * 2 + 1;                //找孩子
	while (child < _con.size())
    {
	    if (child + 1 < _con.size() &&
			com(_con[child], _con[child + 1]))  //根据优先级找最符合的还在
		{
			child++;
		}

		if (com(_con[parent], _con[child]))      //判断是否符合优先级
		{
			std::swap(_con[parent], _con[child]);  //符合则交换
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

其他功能

接口补齐

🍾之后将剩余的接口补齐即可,分别是堆顶元素、堆的大小、判空和交换。

const T& top()
{
	return _con[0];
}

size_t size()
{
	return _con.size();
}

bool empty()
{
	return _con.empty();
}

void swap(priority_queue& pq)
{
	_con.swap(pq._con);
}

迭代器区间构造

🍾在看文档的时候,还看到通过迭代器区间进行构造,于是便简单实现一下,同时还要写一个无参的默认构造函数。

priority_queue()
{}

template<class interator>
priority_queue(interator begin, interator end)  //迭代器区间构造
{
	while (begin != end)
	{
		push(*begin);            //将每个值push进堆中
		begin++;
	}
}

🍾好了,今天 priority_queue基本使用和模拟实现 的相关内容到这里就结束了,如果这篇文章对你有用的话还请留下你的三连加关注。文章来源地址https://www.toymoban.com/news/detail-481430.html

到了这里,关于【STL】priority_queue的使用及模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】priority_queue使用与模拟实现

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸C++  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同

    2024年02月16日
    浏览(43)
  • 《priority_queue的模拟实现》

    本文主要介绍 所谓的仿函数(functor),是通过重载 () 运算符模拟函数形为的类。 因此,这里需要明确两点: 仿函数不是函数,它是个类; 仿函数重载了()运算符,使得它的对你可以像函数那样子调用(代码的形式好像是在调用函数)。(C语言中就是函数指针) 为了适应更多的

    2024年02月07日
    浏览(37)
  • 优先级队列priority_queue模拟实现

    🌟🌟hello,各位读者大大们你们好呀🌟🌟 🚀🚀系列专栏:【C++的学习】 📝📝本篇内容:C++容器优先级队列priority_queue模拟实现 ⬆⬆⬆⬆上一篇:string模拟实现 💖💖作者简介:轩情吖,请多多指教( •̀֊•́ ) ̖́- ①优先级队列是一种容器适配器,它的第一个元素总是

    2024年02月02日
    浏览(44)
  • 【C++】STL使用仿函数控制优先级队列priority_queue

    本文章讲解C++STL的容器适配器:priority_queue的实现,并实现仿函数控制priority_queue底层。 priority_queue叫做优先级队列,它的底层结构是堆,在库中,默认生成的是大堆 在库的实现中,使用vector作为该优先级队列的适配容器。 由于priority_queue也是一个适配器,所以它的接口函数

    2024年02月16日
    浏览(48)
  • C++:模版进阶 | Priority_queue的模拟实现

                                                创作不易,感谢三连支持  模板参数分类为 类型形参与非类型形参 。 类型形参即:出现在模板参数列表中,跟在class或者typename之类的参数类型名称。 非类型形参,就是 用一个常量作为类(函数)模板的一个参数 ,在类(函数

    2024年03月12日
    浏览(44)
  • [C++]priority_queue的介绍及模拟实现

    目录 priority_queue的介绍及模拟实现::                                                         priority_queue的介绍                                                         priority_queue的定义方式                 

    2024年02月04日
    浏览(45)
  • 【C++初阶】模拟实现优先级队列priority_queue

    👦个人主页:@Weraphael ✍🏻作者简介:目前学习C++和算法 ✈️专栏:C++航路 🐋 希望大家多多支持,咱一起进步!😁 如果文章对你有帮助的话 欢迎 评论💬 点赞👍🏻 收藏 📂 加关注✨ 优先级队列顾名思义就是 按优先级出队列 priority_queue 是一个容器适配器,默认使用

    2024年02月10日
    浏览(40)
  • 【STL】priority_queue(优先级队列)详解及仿函数使用(附完整源码)

    1. priority_queue介绍和使用 1.1 priority_queue介绍 优先级队列也是在 queue 里: 因此和 queue 一样, priority_queue 也是一个容器适配器。priority_queue官方文档 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。 类似于堆,在堆中可以随

    2024年02月08日
    浏览(42)
  • C++ STL priority_queue

    目录 一.认识priority_queue 二. priority_queue的使用 三.仿函数  1.什么是仿函数  2.控制大小堆  3.TopK问题 四.模拟实现priority_queue  1.priority_queue的主要接口框架  2.堆的向上调整算法  3.堆的向下调整算法  4.仿函数控制大小堆  五.priority_queue模拟实现整体代码和测试 priority_queue-

    2024年02月07日
    浏览(43)
  • 【C++】priority_queue模拟实现过程中值得注意的点

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 本篇文章旨在记录博主在模拟实现priority_queue适配器中遇到的一些问题,希望与大家

    2024年01月23日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包