c++--priority_queue和仿函数

目录
1.priority_queue
实现:
2.仿函数
priority_queue+仿函数 实现代码
1.priority_queue

优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的,其实就是个堆,默认是大根堆。

优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。
简单实现:
#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace ch
{template <class T, class Container = vector<T>>class priority_queue{public:priority_queue(){}void adjust_up(int child) //向上调整算法{size_t parent = (child - 1) / 2;while (child > 0){if (c[parent] < c[child]){swap(c[parent], c[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent) //向下调整算法{size_t child = parent * 2 + 1;while (child < c.size()){if (child + 1 < c.size() && c[child] < c[child + 1]){child++;}if (c[parent] < c[child]){swap(c[parent], c[child]);parent = child;child = parent * 2 + 1;}else{break;}}}template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){c.push(*first);first++;}for (int i = (c.size() - 1 - 1) / 2; i >= 0; i--) //建堆,时间复杂度为O(N){adjust_down(i);}}bool empty() const{return c.empty();}size_t size() const{return c.size();}const T& top(){return c[0];}void push(const T& x){c.push_back(x);adjust_up(c.size() - 1);}void pop(){swap(c[0], c[c.size() - 1]);c.pop_back();adjust_down(0);}private:Container c;};};
引入仿函数实现定义类型时就能决定大小堆
2.仿函数
就是定义一个类,类中只有一个重载了()的成员函数,可以有传入参数,需要调用时创建其对象,如:
class Print{void operator()(){cout<<"hehe"<<endl;}};
int main(){Print p;p();}
所以我们写个大于小于逻辑的仿函数,并在创建priority_queue时传入此类即可
priority_queue+仿函数 实现代码
//小于仿函数template<class T>class myless {public:bool operator()(const T& x,const T& y) {return x < y;}};//大于仿函数template<class T>class mygreater {public:bool operator()(const T& x, const T& y) {return x > y;}};template <class T, class Container = vector<T>, class Compare = myless<T> >class priority_queue{public:priority_queue() = default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last) {while (first != last) {c.push_back(*first);first++;}for (int i = (size()-1-1) / 2; i >= 0; i--) {adjust_down(i);}}bool empty() const {return c.empty();}size_t size() const {return c.size();}const T& top() const {assert(!empty());return c[0];}void adjust_up(size_t child) {while (child > 0) {size_t parent = (child - 1) / 2;if (comp(c[parent] , c[child])) {swap(c[parent], c[child]);}else {break;}child = parent;}}void push(const T& x) {c.push_back(x);adjust_up(c.size()-1);}void adjust_down(size_t parent) {size_t child = parent * 2 + 1;while (child < size()) {if (child + 1 < size() && comp(c[child] , c[child + 1])) {child++;}if (comp(c[parent] , c[child])) {swap(c[child], c[parent]);parent = child;child = child * 2 + 1;}else {break;}}}void pop() {assert(!empty());swap(c[0], c[size() - 1]);c.erase(c.end()-1);adjust_down(0);}private:Container c;Compare comp;};
相关文章:
c++--priority_queue和仿函数
目录 1.priority_queue 实现: 2.仿函数 priority_queue仿函数 实现代码 1.priority_queue 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的,其实就是个堆,默认是大根堆。…...
Harmony os Next——关系型数据库relationalStore.RdbStore的使用
Harmony os Next——关系型数据库relationalStore.RdbStore的使用 描述数据库的使用建表定义表信息创建数据库表 创建数据库操作对象增更新查询删数据库的初始化 描述 本文通过存储一个简单的用户信息到数据库中为例,进行阐述relationalStore.RdbStore数据库的CRUD…...
快手直播限流怎么办?
直播限流怎么办?这期把直播间限流的所有原因都讲得明明白白,如果你直播间昨天还播的好好的,今天突然间贴地飞行,按照这个思路框架去排查,准没问题。 第一件事情肯定是排查一下评分问题, 信用分、口碑分、…...
【MySQL】数据库入门基础
文章目录 一、数据库的概念1. 什么是数据库2. 主流数据库3. mysql和mysqld的区别 二、MySQL基本使用1. 安装MySQL服务器在 CentOS 上安装 MySQL 服务器在 Ubuntu 上安装 MySQL 服务器验证安装 2. 服务器管理启动服务器查看服务器连接服务器停止服务器重启服务器 3. 服务器&…...
cannot allocate memory in static TLS block
如果不是内存太小,那是不是因为glibc太旧呢? 考虑 glibc 2.22 以后的版本。 glibc-2.22 中加入了如下commit:f8aeae347377f3dfa8cbadde057adf1827fb1d44 https://sourceware.org/git/?pglibc.git;acommit;hf8aeae347377f3dfa8cbadde057adf1…...
Leetcode 654:最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点,其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums 构建的 最大二叉树…...
uniapp小程序src引用服务器图片时全局变量与图片路径拼接
理论上,应该在main.js中定义一个全局变量,然后在页面的<image>标签上的是src直接使用即可 main.js 页面上 看上去挺靠谱的,实际上小程序后台会报一个错 很明显这种方式小程序是不认的,这就头疼了,还想过另外一个…...
比较PWM调光和无极调光
在比较PWM调光和无极调光哪种方式更节能时,需要综合考虑多个因素,如灯具类型、光源效率、调光范围以及使用场景等。 PWM调光系统通过调节LED驱动电流的占空比来实现LED亮度的调节,具有高精度、高稳定性、无闪烁现象以及适用范围广等优点。其节…...
【高校科研前沿】新疆生地所陈亚宁研究员团队在GeoSus发文:在1.5°C和2°C全球升温情景下,中亚地区暴露于极端降水的人口增加
目录 文章简介 1.研究内容 2.相关图件 3.文章引用 文章简介 论文名称:Increased population exposures to extreme precipitation in Central Asia under 1.5 ◦C and 2 ◦C global warming scenarios(在1.5C和2C全球变暖情景下,中亚地区…...
使用 OKhttp3 实现 智普AI ChatGLM HTTP 调用(SSE、异步、同步)
SSE 调用 SSE(Sever-Sent Event),就是浏览器向服务器发送一个HTTP请求,保持长连接,服务器不断单向地向浏览器推送“信息”(message),这么做是为了节约网络资源,不用一直…...
智慧校园教学模式的崛起:优化学习体验
在当今数字化时代,智慧校园教学模式正在成为教育界的热门话题。随着科技的不断发展,传统的教学方式已经无法满足现代学生的需求。智慧校园教学模式以其灵活性、互动性和个性化的特点,正逐渐改变着教育的面貌。 首先,智慧校园教学模…...
ffmpeg视频编码原理和实战-(5)对编码过程进行封装并解决丢帧问题
头文件: xencode.h #pragma once #include <mutex> #include<vector> struct AVCodecContext; struct AVPacket; struct AVFrame; class XEncode { public:///// 创建编码上下文/// para codec_id 编码器ID号,对应ffmpeg/// return 编码上…...
halo进阶-主题插件使用
开始捣鼓捣鼓halo,换换主题,加个页面 可参考:Halo 文档 安装/更新主题 主题如同壁纸,萝卜青菜各有所爱,大家按需更换即可; Halo好在一键更换主题,炒鸡方便。 安装/更新插件 此插件还扩展了插件…...
资深开发推荐的IDEA 插件
开发如虎添翼 工欲善其事,必先利其器。想要提升编程开发效率,必须选择一款顺手的开发工具,插件不在多,而在精,作为从业10年的程序员,我目前用到这十几个插件,在平时开发,代码review…...
数学题目系列(一)|丑数|各位和|埃氏筛|欧拉筛
一.丑数 链接:丑数 分析: 丑数只有2,3,5这三个质因数,num 2a 3b 5c也就是一个丑数是由若干个2,3,5组成,那么丑数除以这若干个数字最后一定变为1 代码 class Solution {publi…...
k8s学习--Secret详细解释与应用
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 Secret什么是Secret?Secret四种类型及其特点Secret应用案例(1)将明文密码进行base64编码(2)编写创建secret的YAML文…...
功能问题:如何防止接口重复请求?
大家好,我是大澈! 本文约 1400 字,整篇阅读约需 3 分钟。 防止接口重复请求在软件开发中非常重要,重复请求必然会导致服务器资源的浪费。 因为每次请求都需要服务器进行处理,如果请求是重复的,那么服务…...
系统架构设计师【第5章】: 软件工程基础知识 (核心总结)
文章目录 5.1 软件工程5.1.1 软件工程定义5.1.2 软件过程模型5.1.3 敏捷模型5.1.4 统一过程模型(RUP)5.1.5 软件能力成熟度模型 5.2 需求工程5.2.1 需求获取5.2.2 需求变更5.2.3 需求追踪 5.3 系统分析与设计5.3.1 结构化方法5.3.2 面向对象…...
嵌入式Linux系统编程 — 2.2 标准I/O库:检查或复位状态
目录 1 检查或复位状态简介 2 feof()函数 2.1 feof()函数简介 2.2 示例程序 3 ferror()函数 4 clearerr()函数 4.1 clearerr()函数简介 4.2 示例程序 1 检查或复位状态简介 调用 fread() 函数读取数据时,如果返回值小于参数 nmemb 所指定的值,这…...
pESC-HIS是什么,怎么看?-实验操作系列-2
01 典型的pESC-HIS质粒遗传图谱 02 介绍 质粒类型:酿酒酵母蛋白表达载体 表达水平:高拷贝 诱导方法:半乳糖 启动子:GAL1和GAL10 克隆方法:多克隆位点,限制性内切酶 载体大小:6706bp 5 测…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
2025年- H71-Lc179--39.组合总和(回溯,组合)--Java版
1.题目描述 2.思路 当前的元素可以重复使用。 (1)确定回溯算法函数的参数和返回值(一般是void类型) (2)因为是用递归实现的,所以我们要确定终止条件 (3)单层搜索逻辑 二…...
大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程
基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...
