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 测…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
