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 测…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...
