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

优先级队列(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()

  1. 将数据插入到容器的尾端
  2. 进行向上调整算法,建成堆
	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内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

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

    1 stack 1.1 stack 介绍 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:empty:判空操作.back:获取尾部元素操作.pus

  • C++ STL priority_queue自定义排序实现方法详解

    前面讲解 priority_queue 容器适配器时,还遗留一个问题,即当 <function> 头文件提供的排序方式(std::less<T> 和 std::greater<T>)不再适用时,如何自定义一个满足需求的排序规则. 首先,无论 priority_queue 中存储的是基础数据类型(int.double 等),还是 string 类对象或者自定义的类对象,都可以使用函数对象的方式自定义排序规则.例如: #include<iostream> #in

  • C++ 中"priority_queue" 优先级队列实例详解

    C++ 中"priority_queue" 优先级队列实例详解 1. 简介 标准库队列使用了先进先出(FIFO)的存储和检索策略. 进入队列的对象被放置在尾部, 下一个被取出的元素则取自队列的首部. 标准库提供了两种风格的队列: FIFO 队列(FIFO queue, 简称 queue), 以及优先级队列(priority queue). priority_queue 允许用户为队列中存储的元素设置优先级. 这种队列不是直接将新元素放置在队列尾部, 而是放在比它优先级低的元素前面. 标

  • c++优先队列(priority_queue)用法详解

    普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除. 在优先队列中,元素被赋予优先级.当访问元素时,具有最高优先级的元素最先删除.优先队列具有最高级先出 (first in, largest out)的行为特征. 首先要包含头文件#include<queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队. 优先队列具有队列的所有特性,包括队列的基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的. 和队列基本

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

    优先级队列(Priority Queue) 队列是一种特征为FIFO的数据结构,每次从队列中取出的是最早加入队列中的元素.但是,许多应用需要另一种队列,每次从队列中取出的应是具有最高优先权的元素,这种队列就是优先级队列(Priority Queue),也称为优先权队列. 1. 优先级队列的概念 优先级队列的定义 优先级队列是不同于先进先出队列的另一种队列.每次从队列中取出的是具有最高优先权的元素. 优先级队列的特点 优先级队列是0个或多个元素的集合,每个元素都有一个优先权或值. 当给每个元素分配

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

    目录 适配器 stack容器适配器 ️stack的介绍 ️stack的使用 ️stack的模拟实现 queue ️queue的介绍 ️queue的使用 ️queue的模拟实现 deque容器 priority-queue ️priority-queue的使用 ️priority-queue的模拟实现 适配器 适配器是一种设计模式(设计模式是一套被反复使用的.多数人知晓的.经过分类编目的.代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口.例如: 容器适配器让一种已存在的容

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

    目录 一. 什么是适配器与容器适配器? 二. 理解容器适配器 stack的模拟实现 queue的模拟实现 一. 什么是适配器与容器适配器? 适配器是一种设计模式(设计模式是一套被反复使用的,多数人知晓的,经过分类编目的,代码设计经验的总结),该种模式将一个类的接口转换成用户需要的另外一个接口. 举个例子:在日常生活中,当手机没电了,我们需要给手机充电,给手机充电的方式很多,可以插到电源上,也可以用充电宝,还可以直接连着电脑充.而我们并不关心用什么给它充电,我们关心的只是能否给手机充上电.适配器充

  • 优先队列(priority_queue)的C语言实现代码

    优先队列(priority_queue)和一般队列(queue)的函数接口一致,不同的是,优先队列每次出列的是整个队列中最小(或者最大)的元素. 本文简要介绍一种基于数组二叉堆实现的优先队列,定义的数据结构和实现的函数接口说明如下: 一.键值对结构体:KeyValue 复制代码 代码如下: // =============KeyValue Struct==================================typedef struct key_value_struct KeyValu

  • 微信小程序 视图容器组件的详解及实例代码

    微信小程序 视图容器组件详解: 小程序给出的视图容器组件有三个:</view>.</scroll-view>和</swiper>: 1.</view> 视图容器 </view>相当于html中的</div>标签,有四个属性: hover和hover-class与点击效果有关:hover设置是否启用点击效果,而hover-class设置点击的效果. hover-start-time和hover-stay-time与点击效果的时间有关:h

  • C++利用容器查找重复列功能实现

    复制代码 代码如下: # include <vector> # include <iostream> # include <set> using namespace std; int main(int argc, char * argv[]) { vector<int> v; //找一些数据来测试 for (int i = 0; i < 50; i++) v.push_back(rand() % 25); for (int i = 0; i <

  • c++中容器之总结篇

    C++中的容器大致可以分为两个大类:顺序容器和关联容器.顺序容器中有包含有顺序容器适配器. 顺序容器:将单一类型元素聚集起来成为容器,然后根据位置来存储和访问这些元素.主要有vector.list.deque(双端队列).顺序容器适配器:stack.queue和priority_queue. 关联容器:支持通过键来高效地查找和读取元素.主要有:pair.set.map.multiset和multimap. 接下来依次对于各种容器做详细的介绍. 一.顺序容器 1.顺序容器定义 为了定义一个容器类型

  • C++ STL关联式容器自定义排序规则的2种方法

    前面在讲解如何创建 map.multimap.set 以及 multiset 容器时,遗留了一个问题,即如何自定义关联式容器中的排序规则? 实际上,为关联式容器自定义排序规则的方法,已经在 <STL priority_queue自定义排序方法>一节中做了详细的讲解.换句话说,为 Priority_queue 容器适配器自定义排序规则的方法,同样适用于所有关联式容器. 总的来说,为关联式容器自定义排序规则,有以下 2 种方法. 1) 使用函数对象自定义排序规则 在掌握此方法之前,读者必须对函数对

随机推荐