<C++> 优先级队列

目录

前言

一、priority_queue的使用

1. 成员函数

2. 例题

二、仿函数

三、模拟实现

1.  迭代器区间构造函数 && AdjustDown

2. pop

3.  push && AdjustUp

4. top

5. size

6. empty

 四、完整实现

总结


前言

        优先级队列以及前面的双端队列基本上已经脱离了队列定义,只是占了队列名字

优先级队列——priority_queue

1. 优先级队列是一种容器适配器,根据一些严格的弱排序标准,经过专门设计,其第一个元素始终是它所包含的最大元素。

2. 此上下文类似于堆,其中元素可以随时插入,并且只能检索最大堆元素(优先级队列中顶部的元素)。

3. 优先级队列作为容器适配器实现,容器适配器是使用特定容器类的封装对象作为其基础容器的类,提供一组特定的成员函数来访问其元素。元素从特定容器的“背面”弹出,这称为优先级队列的顶部

4. 底层容器可以是任何标准容器类模板,也可以是一些其他专门设计的容器类。容器应可通过随机访问迭代器访问,并支持以下操作:

  • empty()
  • size()
  • front()
  • push_back()
  • pop_back()


5. 标准容器类vector和deque满足这些要求。默认情况下,如果未为特定priority_queue类实例化指定容器类,则使用标准容器vector。

6. 需要支持随机访问迭代器,以便始终在内部保持堆结构。这是由容器适配器通过自动调用算法函数 make_heap、push_heap、pop_heap 自动完成的,并在需要时完成。

注意:

  • priority_queue还是适配器,但是适配的是vector
  • 底层是二叉树的堆
  • priority_queue仍然包括在queue头文件中 
  • 默认大堆
  • Compare的缺省是less,表示的是大根堆

        可以使用仿函数修改为小根堆

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

一、priority_queue的使用

1. 成员函数

2. 例题

215. 数组中的第K个最大元素

方法一:直接使用sort排序

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        sort(nums.begin(), nums.end(), greater<int>());
        return nums[k - 1];
    }
};

 方法二:优先级队列,建大堆

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();
    }
};

方法三:维护一个有K个数据的小堆,遍历nums数组,若比top()值大,就入堆,最后返回top()数据

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);
        for (int i = k; i < nums.size(); ++i)
        {
            if (nums[i] > pq.top())
            {
                pq.pop();
                pq.push(nums[i]);
            }
        }

        return pq.top();
        
    }
};

注意:

        sort函数最后一个参数是greater<int>(),是一个匿名对象,而在priority_queue<>内部,第三个模板是greater<int>,是类型,不能加括号

二、仿函数

        我们在之前就遇到过sort函数如果想实现降序,需要加上仿函数greater<类型>(),那么什么是仿函数呢?它又有什么作用?

我们来看一个简单的例子:

class Fun
{
public:
	bool operator()(int a, int b)
	{
		return a < b;
	}
};

int main()
{     
    Fun func;
    cout << func(1, 2) << endl;
    //等价于
    cout << func.operator()(1, 2) << endl;

    return 0;
}
  • 这里的Fun就是仿函数,由Fun类定义的对象称为函数对象
  • 仿函数,顾名思义,一个类的对象可以像函数一样使用,它替代了c语言里的函数指针,我们只需要重载 () 符号就可以像使用函数一样调用它的 () 运算符重载函数

那么这样的仿函数有什么作用呢?

  •  替代c语言的函数指针,因为c语言的函数指针很复杂、容易出错
  • 搭配模板可以实现多类型的函数运算,不会将函数“写死”,例如:我们写Less、Greater类,重载()符号,在需要的地方实例化函数对象,如果有比较大小的情况就使用函数对象(参数1,参数2),原理就是调用operator()函数,像函数一样调用

下面是priority_queue带上第三个模板参数Less后使用仿函数的代码:

template<class T>
class Less
{
public:
	bool operator()(const T& a, const T& b)
	{
		return a < b;
	}
};

template<class T>
class Greater
{
public:
	bool operator()(const T& a, const T& b)
	{
		return a > b;
	}
};

namespace my_priority_queue
{
	// Less<T> 才是Less类的类型
	template<class T, class Container = vector<T>, class Compare = Less<T>>
	class priority_queue
	{
	private:
		//大堆,向下调整
		void AdjustDown(int parent)
		{
			//创建函数对象,Less模板类型就是<比较,Greater模板类型就是>比较
			Compare com;

			//找左右孩子中最大的哪一个
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				//因为com是比较小于关系,所以需要将原先大于的表达式逆一下
				
				//判断右孩子是否存在
				/*if (child + 1 < _con.size() && _con[child + 1] > _con[child])*/
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}

				//if (_con[child] > _con[parent])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}

		}

		void AdjustUp(int child)
		{
			Compare com;

			int parent = (child - 1) / 2;
			while (child > 0)	//最坏情况:孩子等于0时结束
			{
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = child - 1 >> 1;
				}
				else
				{
					break;
				}
			}
		}

	public:
		template<class InputIterator>	//input只写迭代器

		//迭代器区间构造函数
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}

			//建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i )
			{
				AdjustDown(i);
			}
		}

		void pop()
		{
			//交换后,尾删,并向下调整
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}

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

	private:
		//容器
		Container _con;
	};
}

        如果比较的类型是其他自定义类型,并且该类没有重载operator<函数,那么我们就需要手写一个仿函数进行比较,否则编译错误,无法进行比较

       因为库里的仿函数使用了模板,是什么类型就按什么类型相比,那么如果是new返回的指针类型,由于每次new返回的地址相当于是随机的,又比较的是指针类型的大小,所以比较结果也是随机结果。所以我们还是需要写仿函数,修改比较方式,去比较指针指向的内容即可。

三、模拟实现

编译错误,找不到出错位置怎么办?

        如果代码编译错误,找不到在哪,那么逐步屏蔽掉一些代码,逐步排查,是十分有效的找到错误处方法

        priority_queue也同queue、stack一样,是适配器,适配vector容器

1.  迭代器区间构造函数 && AdjustDown

  • 采用封装容器vector的push_back尾插数据,因为默认是大堆,向下建堆,所以尾插数据后,将从最后一个元素的父亲结点—— (_con.size() - 1 - 1) / 2 开始向下调整。
  • 向下调整函数不用多说,在二叉树部分我们详细讲解过
namespace my_priority_queue
{
	// Less<T> 才是Less类的类型
	template<class T, class Container = vector<T>, class Compare = Less<T>>
	class priority_queue
	{
	private:
		//大堆,向下调整
		void AdjustDown(int parent)
		{
			//创建函数对象,Less模板类型就是<比较,Greater模板类型就是>比较
			Compare com;

			//找左右孩子中最大的哪一个
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				//因为com是比较小于关系,所以需要将原先大于的表达式逆一下
				
				//判断右孩子是否存在
				/*if (child + 1 < _con.size() && _con[child + 1] > _con[child])*/
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}

				//if (_con[child] > _con[parent])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}

		}

	public:
		template<class InputIterator>	//input只写迭代器

		//迭代器区间构造函数
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}

			//建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i )
			{
				AdjustDown(i);
			}
		}


	private:
		//容器
		Container _con;
	};
}

 2. pop

  • 堆的pop,将堆顶数据与最后一个数据进行交换,再进行pop_back,再将堆顶数据向下调整
		void pop()
		{
			//交换后,尾删,并向下调整
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();

			AdjustDown(0);
		}

 3.  push && AdjustUp

  • 尾插数据后,将该数据向上调整
		void AdjustUp(int child)
		{
			Compare com;

			int parent = (child - 1) / 2;
			while (child > 0)	//最坏情况:孩子等于0时结束
			{
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = child - 1 >> 1;
				}
				else
				{
					break;
				}
			}
		}

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

 4. top

  • 返回堆顶数据,返回值是 const T&
		const T& top()
		{
			return _con[0];
		}

 5. size

  • 返回vector的size()即可
		size_t size()
		{
			return _con.size();
		}

 6. empty

  • 直接调用vector的empty函数即可
		size_t size()
		{
			return _con.size();
		}

 四、完整实现

#pragma once
#include<iostream>
#include<vector>
#include<functional>
using namespace std;

template<class T>
class Less
{
public:
	bool operator()(const T& a, const T& b)
	{
		return a < b;
	}
};

template<class T>
class Greater
{
public:
	bool operator()(const T& a, const T& b)
	{
		return a > b;
	}
};

namespace my_priority_queue
{
	// Less<T> 才是Less类的类型
	template<class T, class Container = vector<T>, class Compare = Less<T>>
	class priority_queue
	{
	private:
		//大堆,向下调整
		void AdjustDown(int parent)
		{
			//创建函数对象,Less模板类型就是<比较,Greater模板类型就是>比较
			Compare com;

			//找左右孩子中最大的哪一个
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				//因为com是比较小于关系,所以需要将原先大于的表达式逆一下
				
				//判断右孩子是否存在
				/*if (child + 1 < _con.size() && _con[child + 1] > _con[child])*/
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}

				//if (_con[child] > _con[parent])
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}

		}

		void AdjustUp(int child)
		{
			Compare com;

			int parent = (child - 1) / 2;
			while (child > 0)	//最坏情况:孩子等于0时结束
			{
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = child - 1 >> 1;
				}
				else
				{
					break;
				}
			}
		}

	public:

		priority_queue()
		{}

		//迭代器区间构造函数
		template<class InputIterator>	//input只写迭代器
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}

			//建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i )
			{
				AdjustDown(i);
			}
		}

		void pop()
		{
			//交换后,尾删,并向下调整
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();

			AdjustDown(0);
		}

		void push(const T& x)
		{
			_con.push_back(x);

			AdjustUp(_con.size() - 1);
		}

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

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

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

	private:
		//容器
		Container _con;
	};
}

void test_priority_queue1()
{
	// 默认是大堆 -- less
	//priority_queue<int> pq;

	// 仿函数控制实现小堆
	my_priority_queue::priority_queue<int, vector<int>, Greater<int>> pq;

	pq.push(3);
	pq.push(5);
	pq.push(1);
	pq.push(4);

	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

总结

        priority_queue优先级队列就是存储在vector内的堆,掌握向上向下调整函数,可以回顾之前的文章堆的实现一节。

        最后,如果小帅的本文哪里有错误,还请大家指出,请在评论区留言(ps:抱大佬的腿),新手创作,实属不易,如果满意,还请给个免费的赞,三连也不是不可以(流口水幻想)嘿!那我们下期再见喽,拜拜!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/150087.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

单pipeline部署一套代码,多项目

单pipeline部署一套代码&#xff0c;多项目 pipeline {agent anyparameters {gitParameter(name: BRANCH_TAG, type: PT_BRANCH_TAG, branchFilter: origin/(.*), defaultValue: main, selectedValue: DEFAULT, sortMode: DESCENDING_SMART, description: 请选择需要部署的代码…

【Regulatory Genomics】Part2 BPNet、DeepLIFT

文章目录 Deep learning at base-resolution reveals cis-regulatory motif syntaxproblemBPNet: predicting base-resolution profiles from DNA sequenceInterpreting the predictions of BPNet1 DeepLIFT2 TF-MoDISCO3 motif syntax derived TF cooperativity Experimental …

人工智能基础_机器学习036_多项式回归升维实战3_使用线性回归模型_对天猫双十一销量数据进行预测_拟合---人工智能工作笔记0076

首先我们拿到双十一从2009年到2018年的数据 可以看到上面是代码,我们自己去写一下 首先导包,和准备数据 from sklearn.linear_model import SGDRegressor import numpy as np import matplotlib.pyplot as plt X=np.arange(2009.2020)#左闭右开,2009到2019 获取从2009到202…

Python如何使用Pyecharts+TextRank生成词云图?

Python如何使用PyechartsTextRank生成词云图&#xff1f; 1 应用场景2 关于Pyecharts2.1 Pyecharts简介2.2 Pyecharts安装2.3 Pyecharts支持的图形2.4 Pyecharts的一个示例 3 关于TextRank3.1 TextRank简介3.2 TextRank安装 4 词云图的生成过程4.1 导入需要的包4.2 目标文件4.3…

使用c++程序,实现图像平移变换,图像缩放、图像裁剪、图像对角线镜像以及图像的旋转

数字图像处理–实验三A图像的基本变换 实验内容 A实验&#xff1a; &#xff08;1&#xff09;使用VC设计程序&#xff1a;实现图像平移变换&#xff0c;图像缩放、图像裁剪、图像对角线镜像。 &#xff08;2&#xff09;使用VC设计程序&#xff1a;对一幅高度与宽度均相等的…

计算机网络五层协议的体系结构

计算机网络中两个端系统之间的通信太复杂&#xff0c;因此把需要问题分而治之&#xff0c;通过把一次通信过程中涉及的所有问题分层归类来进行研究和处理 体系结构是抽象的&#xff0c;实现是真正在运行的软件和硬件 1.实体、协议、服务和服务访问点 协议必须把所有不利条件和…

Java GUI实现五子棋游戏

五子棋是一种双人对弈的棋类游戏&#xff0c;通常在棋盘上进行。棋盘为 1515 的方格&#xff0c;黑白双方各执棋子&#xff0c;轮流在棋盘的格点上落子&#xff0c;先在横、竖、斜线上形成五个相连的同色棋子者获胜。五子棋规则简单&#xff0c;易学难精&#xff0c;兼具攻防和…

java,springboot钉钉开发连接器,自定义连接器配合流程使用,流程加入连接器,连接器发送参数,然后你本地处理修改值,返回给流程

1.绘制连接器&#xff0c;注意出餐入参的格式&#xff0c; 2.绘制流程&#xff0c;绑定连接器&#xff0c;是提交后出发还是表单值变化后 3.编写本地接口&#xff08;内网穿透&#xff09;&#xff0c;绑定连接器 钉钉开发连接器&#xff0c;自定义连接器配合流程使用&#x…

安防监控系统EasyCVR平台调用hls地址生成流的时间过长,该如何解决?

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台可拓展性强、…

报错缺少class(org.apache.hadoop.hdfs.DistributedFileSystem)

平台报错缺少 java.lang.RuntimeException:java.lang.ClassNotFoundException: Class org.apache.hadoop.hdfs.DistributedFileSystem not found 实则是缺少jar包 hadoop-hdfs-client-3.1.1.3.1.0.0-78.jar 找到对应的jar放到程序的lib中即可

【探索Linux】—— 强大的命令行工具 P.15(进程间通信 —— system V共享内存)

阅读导航 引言一、system V的概念二、共享内存(1) 概念(2) 共享内存示意图(3) 共享内存数据结构 三、共享内存的使用1. 共享内存的使用步骤&#xff08;1&#xff09;包含头文件&#xff08;2&#xff09;获取键值&#xff08;ftok函数&#xff09;&#xff08;3&#xff09;创…

运营商大数据是新时期贷款公司精准拓客的生命!!是企业的灵魂

贷款客户资源主要根据运营商大数据建模分析网站、app等&#xff0c;获取每天的网站实时访客&#xff0c;app活跃用户使用者数据的信息资源。 而贷款客户资源精准获客平台能帮您做的&#xff0c;就是根据用户实时动态轨迹与通信上网数据&#xff0c;锁定潜在意向客户&#xff0…

CAD Exchanger SDK 须知的开发配置--Crack

支持的配置 目录 支持的编程语言 C 支持C# 支持Java支持Python支持JavaScript 支持 CAD Exchanger SDK 是一组跨平台库&#xff0c;目前支持下列配置。随着时间的推移&#xff0c;旧版本的编译器、体系结构或依赖的第三方库从主要支持级别变为次要支持级别&#xff0c;然后被弃…

竞赛选题 深度学习花卉识别 - python 机器视觉 opencv

文章目录 0 前言1 项目背景2 花卉识别的基本原理3 算法实现3.1 预处理3.2 特征提取和选择3.3 分类器设计和决策3.4 卷积神经网络基本原理 4 算法实现4.1 花卉图像数据4.2 模块组成 5 项目执行结果6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &a…

天津专升本新版报名系统网上报名、填志愿、缴费、审核等操作步骤

天津高职升本网上报名、填报志愿新版专升本报名系统 ▏报名入口&#xff1a;www.zhaokao.net▏注意&#xff1a;一定要在截止时间内完成报名、填报志愿、缴费、审核、下载《报名信息表》等4步骤▏可报考院校及专业请参考招生院校发布的通知&#xff08;招生简章、报考须知&…

数据备份软件调研与使用

目录 目的 Filezilla工具介绍&#xff1a; 获取地址 安装步骤 ①下载客户端和服务端​编辑 ②服务端server上传至目标服务器 安装服务端 server端登录 server配置 安装client 遇到的问题FAQ&#xff1a; ​编辑文档 目的 为确保企业数据安全、避免被非法入侵、数据…

【LabVIEW学习】1.对labview的初步使用,控制数据流动,快捷键,参考手册打不开怎么办

一。初步使用labview 1.程序图标 2.打开之后继续点击新建VI 原因&#xff1a;最后的程序后缀就是 .vi 3.新建之后&#xff0c;会有三个界面&#xff08;没有不要紧&#xff0c;找找肯定有&#xff09; 4.程序操作方法 1.拖动控件到前面板 2.此时程序框图会出现对应的控件 拖动…

PostGIS学习教程六:几何图形(geometry)

文章目录 一、介绍二、元数据表三、表示真实世界的对象3.1、点&#xff08;Points&#xff09;3.2、线串&#xff08;Linestring&#xff09;3.3、多边形&#xff08;Polygon&#xff09;3.4、图形集合&#xff08;Collection&#xff09; 四、几何图形输入和输出五、从文本转换…

【Proteus仿真】【Arduino单片机】DS18B20温度计

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器&#xff0c;使用PCF8574、LCD1602液晶、DS18B20温度传感器等。 主要功能&#xff1a; 系统运行后&#xff0c;LCD1602显示传感器采集温度。 二、软件设计 /*…

模拟业务流程+构造各种测试数据,一文带你测试效率提升80%

&#x1f4e2;专注于分享软件测试干货内容&#xff0c;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01;&#x1f4e2;交流讨论&#xff1a;欢迎加入我们一起学习&#xff01;&#x1f4e2;资源分享&#xff1a;耗时200小时精选的「软件测试」资…