C++ STL priority_queue

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

目录

一.认识priority_queue

二. priority_queue的使用

三.仿函数

 1.什么是仿函数

 2.控制大小堆

 3.TopK问题

四.模拟实现priority_queue

 1.priority_queue的主要接口框架

 2.堆的向上调整算法

 3.堆的向下调整算法

 4.仿函数控制大小堆

 五.priority_queue模拟实现整体代码和测试


一.认识priority_queue

priority_queue----reference

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

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

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

二. priority_queue的使用

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

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

测试:

#include<queue>
#include<iostream>
using namespace std;
int main()
{
	//够一个空的优先级队列
	priority_queue<int> pri_q;
	//插入数据
	pri_q.push(2);
	pri_q.push(27);
	pri_q.push(25);
	pri_q.push(244);
	pri_q.push(212);
	pri_q.push(9);
	
	//连续取出堆顶数据打印
	while (!pri_q.empty())
	{
		cout << pri_q.top()<<' ';
		pri_q.pop();
	}
	return 0;
}

C++ STL priority_queue,c++,开发语言

 三.仿函数

如果我们像控制优先级队列是大堆排,还是小堆排,就需要我们使用放仿函数去控制。

1.什么是仿函数

首先仿函数是一个类,它重载了括号运算符,在使用的时候,定义出对象,就像函数一样使用。

例如:

//仿函数
template<class T>
struct Add
{
	int operator()(int e1, int e2)
	{
		return e1 + e2;
	}
};

int main()
{
	Add<int> add;
	cout << add(10, 20) << endl;

	return 0;
}

C++ STL priority_queue,c++,开发语言

 2.控制大小堆

在头文件<functional>中包含了两个仿函数,less和granter。

less是判断小于的仿函数,对应堆排出来是大堆,granter是判断大于的仿函数,对应堆排出来是小堆。

#include<queue>
#include<functional>
#include<iostream>
using namespace std;
int main()
{
	//小堆
	priority_queue<int,vector<int>,greater<int>> small_q;
	//插入数据
	small_q.push(2);
	small_q.push(27);
	small_q.push(25);
	small_q.push(244);
	small_q.push(212);
	small_q.push(9);
	
	//连续取出堆顶数据打印
	while (!small_q.empty())
	{
		cout << small_q.top()<<' ';
		small_q.pop();
	}
	cout  << endl;
	//大堆
	priority_queue<int, vector<int>, less<int>> big_q;
	//插入数据
	big_q.push(2);
	big_q.push(27);
	big_q.push(25);
	big_q.push(244);
	big_q.push(212);
	big_q.push(9);

	//连续取出堆顶数据打印
	while (!big_q.empty())
	{
		cout << big_q.top() << ' ';
		big_q.pop();
	}

	return 0;
}

C++ STL priority_queue,c++,开发语言

 3.TopK问题

这个问题我们在数据结构二叉树堆的部分已经详细的分析了,感兴趣的可以去看看:数据结构---二叉树---堆

四.模拟实现priority_queue

1.priority_queue的主要接口框架

template<class T, class Continer = vector<T>>
class Priority_queue
{
public:
	//插入数据
	void push(const T& val)
	{
		_con.push_back(val);
		//向上调整
		adjust_up(_con.size() - 1);
	}

	//删除数据
	void pop()
	{
		std::swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		//向下调整
		adjust_down(0);
	}

	//返回栈顶数据
	const T& top()
	{
		return _con[0];
	}

	//判断栈是否为空
	bool empty()
	{
		return _con.empty();
	}

private:
	Continer _con;//适配容器,默认是vector
};

2.堆的向上调整算法

C++ STL priority_queue,c++,开发语言

堆的插入需要保证插入以后还是一个堆,所以这里用到了向上调整算法

在数组中就是,插入一个数在数组的尾上,再通过向上调整算法,调整到合适的位置。

在以堆的角度来看(小堆)为例,将新插入的值看作孩子与其父亲位置的值比较,如果比父亲位置的值还要小,那就将该值与父亲位置的值进行交换,交换后将父亲位置当作新的孩子,继续与其父亲位置的值比较,这样一直向上比较并交换,直到父亲位置的值比自己小或该位置已经没有父亲了,调整结束。

C++ STL priority_queue,c++,开发语言

    //向上调整算法
	void adjust_up(size_t child)
	{
		//1.计算父亲
		size_t parent = (child - 1) / 2;
		while (child > 0)
		{
			//如果孩子比父亲大,就交换,否则就直接推出
			if (_con[parent]< _con[child])
			{
				swap(_con[parent], _con[child]);
				//交换之后,父亲成为新的孩子,继续算新的父亲,直到没有孩子了
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

3.堆的向下调整算法

向下调整算法(大堆为例):从第一个结点开始,找到其孩子结点中较大的一个与父亲位置进行交换,然后将孩子作为新的父亲,再次比较和交换,直到父亲结点比两个结点的值都大或者已经没有孩子了为止。

    //向下调整
	void adjust_down(size_t parent)
	{
		//计算出左孩子
		size_t child = parent * 2 + 1;
		while (child < _con.size())
		{
			//判断是否有右孩子,右孩子是否比左孩子大
			if (child + 1 < _con.size() && _con[child]< _con[child + 1])
			{
				child++;
			}
			//较大的孩子如果比父亲大就交换,否则就直接退出循环
			if (_con[parent]< _con[child])
			{
				swap(_con[child], _con[parent]);
			}
			else
			{
				break;
			}
			//孩子成为新的父亲,继续算出新的孩子
			parent = child;
			child = parent * 2 + 1;
		}
	}

 4.仿函数控制大小堆

//比较小于的仿函数,控制大堆
	template<class T>
	struct less
	{
		bool operator()(const T& val1,const T& val2)
		{
			return val1 < val2;
		}
	};

	//比较大于的仿函数,控制小堆
	template<class T>
	struct grater
	{
		bool operator()(const T& val1, const T& val2)
		{
			return val1 > val2;
		}
	};
    
template<class T, class Continer = vector<T>,class Compare =less<T>>//默认大堆
class Priority_queue
{
public:
    Compare com;
	//插入数据
	void push(const T& val)
	{
		_con.push_back(val);
		//向上调整
		adjust_up(_con.size() - 1);
	}

	//删除数据
	void pop()
	{
		std::swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		//向下调整
		adjust_down(0);
	}

	//返回栈顶数据
	const T& top()
	{
		return _con[0];
	}

	//判断栈是否为空
	bool empty()
	{
		return _con.empty();
	}

private:
	Continer _con;//适配容器,默认是vector
};

 五.priority_queue模拟实现整体代码和测试

Queue.hpp:

    template<class T, class Continer = vector<T>,class Compare =less<T>>
	class Priority_queue
	{
	public:
		Compare com;
		void push(const T& val)
		{
			_con.push_back(val);
			adjust_up(_con.size()-1);
		}

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

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

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


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

	private:
		//向上调整算法
		void adjust_up(size_t child)
		{
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent] , _con[child]))
				{
					swap(_con[parent], _con[child]);

					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		//向下调整
		void adjust_down(size_t parent)
		{
			size_t 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]))
				{
					swap(_con[child], _con[parent]);
				}
				else
				{
					break;
				}
				parent = child;
				child = parent * 2 + 1;
			}
		}

	private:
		Continer _con;
	};
}

main:

#include<iostream>
#include<vector>
#include<list>
using std::vector;
using std::list;
using std::cout;
using std::endl;
using std::swap;

#include"Queue.hpp"
using namespace Qikun;

int main()
{
	//小堆
	Priority_queue<int,std::vector<int>, greater<int>> small_q;
	//插入数据
	small_q.push(2);
	small_q.push(27);
	small_q.push(25);
	small_q.push(244);
	small_q.push(212);
	small_q.push(9);
	
	//连续取出堆顶数据打印
	std::cout << "小堆:";
	while (!small_q.empty())
	{
		cout << small_q.top()<<' ';
		small_q.pop();
	}
	cout  << endl;
	//大堆
	Priority_queue<int, vector<int>, less<int>> big_q;
	//插入数据
	big_q.push(2);
	big_q.push(27);
	big_q.push(25);
	big_q.push(244);
	big_q.push(212);
	big_q.push(9);

	//连续取出堆顶数据打印
	cout << "大堆:";
	while (!big_q.empty())
	{
		cout << big_q.top() << ' ';
		big_q.pop();
	}

	return 0;
}

C++ STL priority_queue,c++,开发语言

 文章来源地址https://www.toymoban.com/news/detail-733612.html

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

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

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

相关文章

  • 【C++】STL使用仿函数控制优先级队列priority_queue

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

    2024年02月16日
    浏览(43)
  • 【C++】STL优先级队列(priority_queue)功能介绍以及模拟实现

    点进来的小伙伴不知道学过数据结构里的堆没有,如果学过的话,那就好说了,优先级队列就是堆,如果没学过,没关系,可以参考一下我之前写的一篇关于堆的博客,可以点进去看看:【数据结构】堆(包含堆排序和TOPK问题) 那么了解过堆了的话,我就不讲那么细致了,

    2024年02月16日
    浏览(45)
  • 【C++】STL中的容器适配器 stack queue 和 priority_queue 的模拟实现

    适配器是一种设计模式 (设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。 例如我们常见的充电器就是一种适配器,它将我们常用的220V交流电压转化为4,5V (或者其他更高的电

    2023年04月26日
    浏览(59)
  • 容器适配器---deque和STL ---stack queue priority_queue的模拟实现 C++

    目录 一、容器适配器 deque原理 deque的缺陷 deque的优势 二、stack的模拟实现  三、queue的模拟实现 四、优先级队列的模拟实现 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户

    2024年02月02日
    浏览(52)
  • 【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

    这篇文章我们接着上一篇的内容,再来学一个STL里的容器适配器—— priority_queue (优先级队列) 1.1 priority_queue的介绍 我们上一篇文章学了 queue (队列),那优先级队列也是在 queue 里面的: 和 queue 一样, priority_queue 也是一个容器适配器,那他和 queue 有什么区别呢?我们一

    2024年02月07日
    浏览(42)
  • STL之priority_queue与仿函数

    1.介绍 函数对象,又称仿函数,是可以像函数一样使用的对象,其原理就是重载了函数调用符: () 因此在此类中,一定有 operator() 的成员函数。 2.示例 如果T是内置类型,则直接进行比较。如果T是自定义类型,则会调用其operator()。 先创建一个_less类型的对象smaller,对于sma

    2024年02月10日
    浏览(38)
  • 【STL】priority_queue的使用及模拟实现

    目录 前言 priority_queue的使用 功能解析 基本接口 写点题目 模拟实现 结构解析 插入删除 调整函数结合仿函数 仿函数介绍 结合使用 其他功能 接口补齐 迭代器区间构造 🍾打开 queue 头文件后,我们发现除了我们之前介绍过的普通队列以外,还有一个 priority_queue 。 🍾其又名为

    2024年02月08日
    浏览(39)
  • 【STL详解 —— priority_queue的使用与模拟实现】

    std::priority_queue 是 C++ 标准库中的容器适配器,它提供了一种基于堆的优先级队列实现。优先级队列是一种特殊的队列,其中的元素按照一定的优先级顺序排列,而不是按照它们被插入的顺序。 在 std::priority_queue 中,插入元素时会根据元素的值自动进行排序,最大(或最小)

    2024年04月17日
    浏览(31)
  • c++11 标准模板(STL)(std::priority_queue)(四)

    template     class T,     class Container = std::vectorT,     class Compare = std::lesstypename Container::value_type class priority_queue; priority_queue 是容器适配器,它提供常数时间的(默认)最大元素查找,对数代价的插入与释出。 可用用户提供的 Compare 更改顺序,例如,用 std::greaterT 将导致最小元

    2024年02月01日
    浏览(43)
  • C++ queue&priority_queue

    目录 一、介绍 二、queue使用 三、模拟实现 四、优先级队列 五、priority_queue使用 OJ题:215. 数组中的第K个最大元素 快速排序 优先级队列 TOPK 六、模拟实现priority_queue 1、仿函数 2、优先级队列类 3、测试函数 1、队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,

    2024年02月01日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包