首页 > 资讯 > 后端开发 > 其他教程 >C++ 容器适配器priority_queue的使用及实现代码

407

分享到

C++ 容器适配器priority_queue的使用及实现代码

2024-04-02 19:04:59 407人浏览泡泡鱼

摘要

优先级队列(Priority Queue) 队列是一种特征为FIFO的数据结构，每次从队列中取出的是最早加入队列中的元素。但是，许多应用需要另一种队列，每次从队列中取出的应是具有最

优先级队列(Priority Queue)

队列是一种特征为FIFO的数据结构，每次从队列中取出的是最早加入队列中的元素。但是，许多应用需要另一种队列，每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列(Priority Queue)，也称为优先权队列。

1. 优先级队列的概念

优先级队列的定义

优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。

优先级队列的特点

优先级队列是0个或多个元素的集合，每个元素都有一个优先权或值。
当给每个元素分配一个数字来标记其优先级时，可设较小的数字具有较高的优先级，这样更方便地在一个集合中访问优先级最高的元素，并对其进行查找和删除操作。
对优先级队列，执行的操作主要有：(1)查找，(2)插入，(3)删除。
在最小优先级队列(min Priority Queue)中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素。
在最大优先级队列(max Priority Queue)中，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。
插入操作均只是简单地把一个新的元素加入到队列中。
注：每个元素的优先级根据问题的要求而定。当从优先级队列中删除一个元素时，可能出现多个元素具有相同的优先权。在这种情况下，把这些具有相同优先权的元素视为一个先来先服务的队列，按他们的入队顺序进行先后处理。

2.优先级队列的使用

头文件：#include < queue >
优先级队列默认是最大优先级队列

接口介绍

函数声明	函数说明
priority_queue() / priority_queue(first, last)	构造一个空的优先级队列
empty( )	判断优先级队列是否为空，为空返回true
empty( )	判断优先级队列是否为空，为空返回true
top( )	获取优先级队列中最大或者最小的元素，即堆顶元素
push(x)	将x元素插入到优先级队列中
pop()	删除优先级队列中最大或者最小的元素，即删除堆顶元素

测试代码：


void test()
{
	priority_queue<int> pq;
	pq.push(13);
	pq.push(14);
	pq.push(9);
	pq.push(23);
	pq.push(12);
	pq.push(22);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

测试结果：默认是最大优先级队列，所以堆顶元素一直是最大的元素

在这里插入图片描述

如何将创建最小优先级队列----
优先级队列原型：
泛型介绍：T为优先级队列存储的数据类型；Container为优先级队列中存储数据的容器；Compare伪函数，决定是最大优先级队列还是最小优先级队列


template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;

创建最小优先级队列：


priority_queue<int, vector<int>, greater<int>> pq;

测试结果：

在这里插入图片描述

优先级队列存放自定义类型时，需要自定义类型支持比较的操作。


class A
{
public:
	A(int a = 1)
		:_a(a)
	{}

	//支持比较函数
	bool operator<(const A& a) const
	{
		return _a < a._a;
	}
	bool operator>(const A& a) const
	{
		return _a > a._a;
	}
	int _a;
};

测试结果：

在这里插入图片描述

应用场景：Top-K问题
数组中的第K个最大元素
代码：


class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        priority_queue<int> pq(nums.begin(), nums.end());
        while (--k)
            pq.pop();
        return pq.top();
    }
};

3.优先级队列的实现

标准容器类vector和deque(双端队列)满足实现优先级队列的需求，库中底层默认是使用Vector容器来实现的，我们现在就利用vector简单模拟实现


private:
	vector<T> con;

向下调整算法

向下调整算法用于优先级队列的删除接口的实现


void shiftDown()
	{
		int parent = 0;
		int child = 2 * parent + 1;
		while (child < con.size())
		{
			if (child + 1 < con.size() && con[child] < con[child + 1])
			{
				++child;
			}
			if (con[parent] < con[child])
			{
				swap(con[parent], con[child]);
				parent = child;
				child = 2 * parent + 1;
			}
			else
			{
				break;
			}
		}
	}

向上调整算法

向上调整算法用于优先级队列的插入接口的实现


//向上调整
	void shiftUp(int child)
	{
		int 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;
			}
		}
	}

push()

将数据插入到容器的尾端
进行向上调整算法，建成堆


	void push(const T& val)
	{
		//尾插
		con.push_back(val);
		shiftUp(con.size() - 1);
	}

pop()

将收尾数据进行交换
删除末尾最后一个元素
进行向下调整算法，建成堆


	void pop()
	{
		//交换
		swap(con[0], con[con.size() - 1]);
		con.pop_back();
		shiftDown();
	}

top()、size()、empty()

都直接使用容器中的接口实现


T& top()
	{
		return con.front();
	}

	size_t size() const
	{
		return con.size();
	}

	bool empty() const
	{
		return con.empty();
	}

测试结果：

在这里插入图片描述

但是我们的实现非常的死板，首先是不能创建最小优先级队列，其次是不能像底层实现一样，可以选择多种容器来存储数据来实现。

解决普通的优先级队列的两个问题

解决只能通过vector< T >来存储数据的问题
我们可以通过容器多添加一个泛型来解决多种容器的存储
priority_queue可以通过 vector< T >、deque< T >实现
默认使用vector< T >
原因：

list不支持随机访问迭代器的方式来访问元素
与deque相比：deque随机访问效率低于vector

与之前代码需要修改的地方
1、泛型


template<class T, class Container = vector<T>>

2、所需要的容器


private:
	Container con;

在这里插入图片描述

解决只能创建最大优先级队列问题
解决办法，加入新的泛型，该泛型是一个伪函数
如果不知道什么是伪函数，可以看看什么是伪函数，以及伪函数的使用
大小堆创建的不同其实就是在实现向上调整和向下调整时元素比较的不同而已。

与之前代码需要修改的地方
1、需要创建两个仿函数类


//用大最小优先级队列
template<class T>
struct Less
{
	bool operator()(const T& a, const T& b)
	{
		return a < b;
	}
};

//用于最小优先级队列
template<class T>
struct Greater
{
	bool operator()(const T& a, const T& b)
	{
		return a > b;
	}
};

2、加入新泛型


template<class T, class Container = vector<T>, class Compare = Less<T>>


private:
	Compare cmp;

3、利用仿函数，替代代码中关键的比较的地方

在这里插入图片描述

测试结果：

在这里插入图片描述

完整代码


//用大最小优先级队列
template<class T>
struct Less
{
	bool operator()(const T& a, const T& b)
	{
		return a < b;
	}
};

//用于最小优先级队列
template<class T>
struct Greater
{
	bool operator()(const T& a, const T& b)
	{
		return a > b;
	}
};

template<class T, class Container = vector<T>, class Compare = Less<T>>
class PriorityQueue
{
public:
	//向下调整
	void shiftDown()
	{
		int parent = 0;
		int child = 2 * parent + 1;
		while (child < con.size())
		{
			if (child + 1 < con.size() && cmp(con[child], con[child + 1]))
			{
				++child;
			}
			if (cmp(con[parent], con[child]))
			{
				swap(con[parent], con[child]);
				parent = child;
				child = 2 * parent + 1;
			}
			else
			{
				break;
			}
		}
	}

	//向上调整
	void shiftUp(int child)
	{
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			if (cmp(con[parent], con[child]))
			{
				swap(con[parent], con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

	void push(const T& val)
	{
		//尾插
		con.push_back(val);
		shiftUp(con.size() - 1);
	}

	void pop()
	{
		//交换
		swap(con[0], con[con.size() - 1]);
		con.pop_back();
		shiftDown();
	}

	T& top()
	{
		return con.front();
	}

	size_t size() const
	{
		return con.size();
	}

	bool empty() const
	{
		return con.empty();
	}
private:
	Container con;
	Compare cmp;
};

到此这篇关于c++ 容器适配器priority_queue的使用及实现的文章就介绍到这了,更多相关C++ 容器适配器priority_queue内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

--结束END--

本文标题: C++ 容器适配器priority_queue的使用及实现代码

本文链接: https://lsjlt.com/news/124140.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

回答

如何调试操作系统的错误？
操作系统

2023-11-15发布

回答

操作系统中的I/O系统是如何实现的？
操作系统

2023-11-15发布

回答

如何实现操作系统的内存管理？
操作系统

2023-11-15发布

回答

什么是虚拟内存，它对操作系统有什么影响？
操作系统

2023-11-15发布

回答

ASP中的MVC架构和WebForms架构有什么区别和使用场景？
ASP.NET

2023-11-15发布

回答

ASP中的数据验证和数据校验有什么不同？
ASP.NET

2023-11-15发布

回答

ASP中的ADO对象和DAO对象有什么区别和使用方法？
ASP.NET

2023-11-15发布

回答

Node.js中的包管理器NPM是什么？如何使用它进行依赖管理？
node.js

2023-11-15发布

回答

Vue.js中的动态组件是什么？如何使用它来动态渲染组件？
VUE

2023-11-15发布

回答

如何使用Vue.js实现懒加载和预加载？
VUE

2023-11-15发布

C++ 容器适配器priority_queue的使用及实现代码

优先级队列(Priority Queue)

1. 优先级队列的概念

优先级队列的定义

优先级队列的特点

2.优先级队列的使用

3.优先级队列的实现

向上调整算法

解决普通的优先级队列的两个问题

C++ 容器适配器priority_queue的使用及实现代码

C++ 容器适配器priority_queue怎么用

C++ STL中的容器适配器实现

C++中priority_queue模拟实现的代码示例

C++ STL容器适配器使用指南

C++ STL中容器适配器怎么实现

C++容器适配与栈的实现及dequeque和优先级详解

C++中priority_queue的使用与模拟实现

Java抽象类、继承及多态和适配器的实现代码

C++中使用FFmpeg适配自定义编码器的实现方法

C# Winform 实现控件自适应父容器大小的示例代码

C#适配器模式的使用

Android列表实现(3)_自定义列表适配器思路及实现代码

Android Spinner与适配器模式详解及实例代码

C++容器适配器的概念与示例

使用go实现适配器模式

Android ListView万能适配器实例代码

Java适配器模式的实现及应用场景

Linux中rm命令使用以及C/C++代码实现

使用C++实现适配器类要注意什么问题

c语言怎么计算字符串长度

c++排序函数sort怎么使用

C++中beginthreadex线程启动不了怎么解决

c语言swap函数如何调用

c++中使用swap函数报错怎么解决

c++中decltype的用法是什么

c语言中sizeof语句怎么使用

C语言怎么实现对文件夹加密

c语言怎么将小数转换成整数

C++中coledatetime函数的用法是什么