优先级队列的实现

什么是优先级队列

优先级队列是一种特殊的数据结构,它类似于队列或栈,但是每个元素都关联有一个优先级或权重。在优先级队列中,元素的出队顺序不是简单地按照它们进入队列的先后顺序(先进先出,FIFO),而是根据元素的优先级来决定。具有最高优先级的元素最先出队,如果两个元素具有相同的优先级,则按照它们在队列中的顺序出队。
通俗来说,假设我们传入队列的是整形数据,那么他会按照数据的从小到大还是从大到小的出队顺序存放在队列中这就是优先级队列

仿函数

这里要提到一个概念叫仿函数
仿函数是一个可以像函数一样调用的对象。简单来说,仿函数是一种具有operator()成员函数的对象,使得该对象可以像普通函数一样使用调用操作符(),他是重载operator()括号实现的,我们来举个例子
下面是个比较大小的仿函数例子

 template<class type>class less{public:bool operator()(const type& x, const type& y){return x < y;}
};

这里我们利用这个比较大小的仿函数,就可以像函数那样调用,就像这样

int main()
{less li;if(li(1,2)){cout<<"y比x大"<<endl;}else{cout<<"x比y大"<<endl;}return 0;}

在举个形象的例子

# include<iostream>
# include<string>
using namespace std;
template<class type>
class _cout
{
public:void operator()(const type& input){cout << input << endl;}
};
int main()
{_cout<string> print;print("hello,word");return 0;
}

有了以上仿函数的介绍之后,就可以开始说我们的优先级队列了

优先级队列的实现

优先级队列的实质上就是用堆来创建队列,按照堆排序的思想来对输入到队列里面的数据进行处理,按照升序建大堆,降序建小堆的思想进行创建,所以这里需要两个堆排序里面关键的函数**adjustdown(向下调整)adjustup(向上调整)**还需要我们上面提到的仿函数,这里仿函数的作用就是我们不用去改代码中的大于还是小于,直接在创建对象的时候提供模板参数就来作为创建大堆还是小堆的依据,非常方便
下面是仿函数

 template<class type>class less{public:bool operator()(const type& x, const type& y){return x < y;}
};template<class type>
class grator
{
public:bool operator()(const type& x, const type& y){return x > y;}
};

接下来是建堆算法

	template<class type,class contier = vector<type>,class compre = less<type>>class priorityqueue{public:void adjustup(size_t child){compre com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent],_con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjustdown(size_t parent){compre com;size_t child = parent * 2 + 1;while (child < _con.size()){//        x        <        y if (child + 1 < _con.size() && com(_con[child], _con[child+1])){child++;}//        x        <        y if (com(_con[parent], _con[child])){ swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}
void push(const type& input)
{_con.push_back(input);adjustup(_con.size() - 1);
}
void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjustdown(0);
}

这里需要结合这4个函数一起看,push就是插入数据,插入完之后,我们这里的默认容器是vector,然后我们调用向上建堆算法,从数组最后一位开始(所以这里的size()-1)vector下标是从零开始的存放10个数就是占用0-9个位置,假设我们插入1,9,2,10,3我们来画图看看是怎么调堆的
在这里插入图片描述这就是向上建堆的过程,也是我们push数据的过程
接下来说一说pop,出队列
这里需先出对顶数据在把第一个数据和最后一个数据进行交换
在这里插入图片描述
在向下调整堆
因为是建的大堆,把最大的数据给pop掉了之后,采用向下调整算法,第二大的数据就会出现在堆顶
在一直执行这个操作,最后的出队顺序就是从大到小的顺序
t1是创建的对象
出队列代码

	void test(){priorityqueue<int,vector<int>,less<int>> t1;t1.push(1);t1.push(9);t1.push(2);t1.push(10);t1.push(3);while (!t1.is_empty()){cout << t1.top() << " ";t1.pop();}}

在这里插入图片描述最后还有剩下的这些小函数关于返回大小,容器空没有,取到堆顶的数据

		size_t size(){return _con.size();}bool is_empty(){return _con.empty();}const type& top(){return _con[0];}

源码

#pragma once
# include<vector>
# include<iostream>
using namespace std;
namespace thr
{ template<class type>class less{public:bool operator()(const type& x, const type& y){return x < y;}
};template<class type>
class grator
{
public:bool operator()(const type& x, const type& y){return x > y;}
};template<class type,class contier = vector<type>,class compre = less<type>>class priorityqueue{public:void adjustup(size_t child){compre com;int parent = (child - 1) / 2;while (child > 0){//        x        <        y if (com(_con[parent],_con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjustdown(size_t parent){compre com;size_t child = parent * 2 + 1;while (child < _con.size()){//        x        <        y if (child + 1 < _con.size() && com(_con[child], _con[child+1])){child++;}//        x        <        y if (com(_con[parent], _con[child])){ swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const type& input){_con.push_back(input);adjustup(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjustdown(0);}size_t size(){return _con.size();}bool is_empty(){return _con.empty();}const type& top(){return _con[0];}private:contier _con;};void test(){priorityqueue<int,vector<int>,less<int>> t1;t1.push(1);t1.push(9);t1.push(2);t1.push(10);t1.push(3);while (!t1.is_empty()){cout << t1.top() << " ";t1.pop();}}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

虚幻5|角色武器装备的数据库学习(不只是用来装备武器,甚至是角色切换也很可能用到)

虚幻5|在连招基础上&#xff0c;给角色添加武器并添加刀光|在攻击的时候添加武器并返回背后&#xff08;第一部分&#xff0c;下一部分讲刀光&#xff09;_unreal 如何给角色添加攻击-CSDN博客 目的&#xff1a;捡起各种不同的武器&#xff0c;捡起的武器跟装备的武器相匹配 …

练习:python条件语句、循环语句和函数的综合运用

需求描述&#xff1a; 期望输出效果&#xff1a; 练习成果&#xff1a; #简单的银行业务流程 many 50000 def main_menu():print("----------主菜单----------"f"\n{name}您好&#xff0c;欢迎来到ATM&#xff0c;请选择操作&#xff1a;""\n查询余…

挑战同档位最强护眼性能,书客L2 Pro革新护眼台灯全新体验!

2024年8月17日&#xff0c;SUKER书客在今日宣布&#xff1a;书客护眼台灯L2 PRO正式发售。书客作为专业护眼台灯实力老牌&#xff0c;主打“医学养护眼”的特性&#xff0c;是唯一做到降低96%近视风险的同时&#xff0c;缓解88%用眼疲劳&#xff0c;光源99.8%高度还原自然光&am…

Ubuntu离线安装docker

查看操作系统版本&#xff1a; rootzyh-VMware-Virtual-Platform:~/install# lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 24.04 LTS Release: 24.04 Codename: noble rootzyh-VMware-Virtual-Platform:~/install#…

删除镜像报子镜像依赖错误

1、删除镜像报子镜像依赖错误 出现这个错误的原因是因为有其他镜像依赖需要删除的镜像。 2解决方法 2.1首先查看无法删除的镜像被哪些镜像所依赖 docker image inspect --format{{.RepoTags}} {{.Id}} {{.Parent}} $(docker image ls -q --filter since${image_id}) # ${ima…

在阿里云上部署 Docker并通过 Docker 安装 Dify

目录 一、在服务器上安装docker和docker compose 1.1 首先关闭防火墙 1.2 安装docker依赖包 1.3 设置阿里云镜像源并安装docker-ce社区版 1.4 开启docker服务并设置开机自启动 1.5 查看docker版本信息 1.6 设置镜像加速 1.7 将docker compose环境复制到系统的bin目录下…

Jmeter接口测试断言详解

&#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 一、响应断言 对服务器的响应接口进行断言校验&#xff0c;来判断接口测试得到的接口返回值是否正确。 二、添加断言 1、apply to&#xff1a; 通常发出一个请…

可视化编程-七巧低代码入门02

1.1.什么是可视化编程 非可视化编程是一种直接在集成开发环境中&#xff08;IDE&#xff09;编写代码的编程方式&#xff0c;这种编程方式要求开发人员具备深入的编程知识&#xff0c;开发效率相对较低&#xff0c;代码维护难度较大&#xff0c;容易出现错误&#xff0c;也需要…

nginx核心配置示例

目录 1、nginx location的详细使用 &#xff08;1&#xff09;精确匹配 &#xff08;2&#xff09;区分大小写 &#xff08;3&#xff09;不区分大小写 &#xff08;4&#xff09;匹配文件名后缀 2、nginx下的用户认证 3、nginx自定义错误页面 4、自定义错误日志 5、n…

WordPress建站之头像及字体错误修正

目录 一、谷歌字体 二、头像网址 三、后续使用中的“坑” 网站建设好以后,会发现有些卡顿,网速好的环境感觉不明写,但是差的环境就难以忍受了。这是打开网页的控制台(Console)会发现有报错信息: 这些报错信息反应了2个问题: 谷歌字体网站无法访问头像网站无法访问下面…

基于Springboot 和Vue 的高校宿舍管理系统源码

网络上很多宿舍管理系统都不完整&#xff0c;大多数缺少数据库文件&#xff0c;所在使用极其不方便&#xff0c;由于本人程序员&#xff0c;根据代码&#xff0c;自己花时间不全了数据库文件&#xff0c;并且可以完美运行&#xff01;&#xff01;&#xff01;&#xff01;&…

基于VS2022+Qt5+C++的串口助手开发

目录 一、前言 二、环境准备 三、创建QT串口项目 ​编辑 四、串口项目实现 1.ui界面设计 2.添加QT串口模块 3.功能实现 ①串口扫描 ②波特率、停止位等设置 ③接收数据 ④发送数据 五、最终效果 六、总结 一、前言 如果有人之前看过我文章的话应该知道&#xf…

Hbase架构和读写流程

目录 1.概述 2.简介 3.Hbase架构 4.数据模型 5.Hbase写流程 6.Hbase读数据 1.概述 本篇文章将简单的讲述Hbase的架构和读写流程&#xff0c;多为理论部分&#xff0c;不涉及API代码 2.简介 从官方介绍可以知道,Hbase是一种分布式、可扩展、支持海量数据存储的 NoSQ…

Element-UI动态生成的表单元素验证示例

模拟数据 tableData: [{name: "系统1",score: 0,children:[{name: "一号子系统",score: 0,}]},{name: "系统2",score: 0,children:[{name: "3号子系统",score: 0,}]},{name: "系统3",score: 0,children:[{name: "5号子…

python-docx在word文件表格中指定行下插入新一行并填充值

from docx import Document from copy import deepcopydef insert_row_after_specific_value(doc, table_index, column_header, target_value, new_row_data):# 加载文档# doc doc_path# 检查表格索引是否有效if table_index > len(doc.tables):print("文档中没有足够…

matlab 音频音量处理(音量大小按照dB调节)

1 音量(声压级)以分贝(dB)表示的计算公式为: 2 % 已知的 x 值 x = 0:-1:-127; % 在这里填入 x 的具体值% 计算 y %y = 10

江理工文档管理系统的设计与实现

TOC springboot148江理工文档管理系统的设计与实现 绪论** 1.1 研究背景 在这个推荐个性化的时代&#xff0c;采用新技术开发一个文档系统来分享和展示内容是一个永恒不变的需求。本次设计的文档管理系统有管理员和用户两个角色。管理员功能有论坛管理&#xff0c;公告管理…

Spark-环境启动

一、概览 从start-all.sh开始捋&#xff0c;一直捋到Master、Worker的启动并建立通信 二、宏观描述 Master端 1、start-all.sh调用start-master.sh启动Master 2、执行org.apache.spark.deploy.master.Master中main方法 3、通过工厂模式创建RpcEnv子类NettyRpcEnv a、创建…

【Vue3】路由Params传参

【Vue3】路由Params传参 背景简介开发环境开发步骤及源码总结 背景 随着年龄的增长&#xff0c;很多曾经烂熟于心的技术原理已被岁月摩擦得愈发模糊起来&#xff0c;技术出身的人总是很难放下一些执念&#xff0c;遂将这些知识整理成文&#xff0c;以纪念曾经努力学习奋斗的日…

【Redis】Linux CentOS Redis 的安装—(一)

Redis 一、获取源二、解压编译 一、获取源 //redis-stable是最新稳定版 wget https://download.redis.io/redis-stable.tar.gz二、解压编译 //我指定目录/app tar -xzvf redis-stable.tar.gz -C /appcd /app/redis-stablemake && make install##三 、修改配置启动 …