当前位置: 首页 > news >正文

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 实现&#xff1a; 2.仿函数 priority_queue仿函数 实现代码 1.priority_queue 优先队列是一种容器适配器&#xff0c;根据严格的弱排序标准&#xff0c;它的第一个元素总是它所包含的元素中最大的&#xff0c;其实就是个堆&#xff0c;默认是大根堆。…...

Harmony os Next——关系型数据库relationalStore.RdbStore的使用

Harmony os Next——关系型数据库relationalStore.RdbStore的使用 描述数据库的使用建表定义表信息创建数据库表 创建数据库操作对象增更新查询删数据库的初始化 描述 本文通过存储一个简单的用户信息到数据库中为例&#xff0c;进行阐述relationalStore.RdbStore数据库的CRUD…...

快手直播限流怎么办?

直播限流怎么办&#xff1f;这期把直播间限流的所有原因都讲得明明白白&#xff0c;如果你直播间昨天还播的好好的&#xff0c;今天突然间贴地飞行&#xff0c;按照这个思路框架去排查&#xff0c;准没问题。 第一件事情肯定是排查一下评分问题&#xff0c; 信用分、口碑分、…...

【MySQL】数据库入门基础

文章目录 一、数据库的概念1. 什么是数据库2. 主流数据库3. mysql和mysqld的区别 二、MySQL基本使用1. 安装MySQL服务器在 CentOS 上安装 MySQL 服务器在 Ubuntu 上安装 MySQL 服务器验证安装 2. 服务器管理启动服务器查看服务器连接服务器停止服务器重启服务器 3. 服务器&…...

cannot allocate memory in static TLS block

如果不是内存太小&#xff0c;那是不是因为glibc太旧呢&#xff1f; 考虑 glibc 2.22 以后的版本。 glibc-2.22 中加入了如下commit&#xff1a;f8aeae347377f3dfa8cbadde057adf1827fb1d44 https://sourceware.org/git/?pglibc.git;acommit;hf8aeae347377f3dfa8cbadde057adf1…...

Leetcode 654:最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点&#xff0c;其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums 构建的 最大二叉树…...

uniapp小程序src引用服务器图片时全局变量与图片路径拼接

理论上&#xff0c;应该在main.js中定义一个全局变量&#xff0c;然后在页面的<image>标签上的是src直接使用即可 main.js 页面上 看上去挺靠谱的&#xff0c;实际上小程序后台会报一个错 很明显这种方式小程序是不认的&#xff0c;这就头疼了&#xff0c;还想过另外一个…...

比较PWM调光和无极调光

在比较PWM调光和无极调光哪种方式更节能时&#xff0c;需要综合考虑多个因素&#xff0c;如灯具类型、光源效率、调光范围以及使用场景等。 PWM调光系统通过调节LED驱动电流的占空比来实现LED亮度的调节&#xff0c;具有高精度、高稳定性、无闪烁现象以及适用范围广等优点。其节…...

【高校科研前沿】新疆生地所陈亚宁研究员团队在GeoSus发文:在1.5°C和2°C全球升温情景下,中亚地区暴露于极端降水的人口增加

目录 文章简介 1.研究内容 2.相关图件 3.文章引用 文章简介 论文名称&#xff1a;Increased population exposures to extreme precipitation in Central Asia under 1.5 ◦C and 2 ◦C global warming scenarios&#xff08;在1.5C和2C全球变暖情景下&#xff0c;中亚地区…...

使用 OKhttp3 实现 智普AI ChatGLM HTTP 调用(SSE、异步、同步)

SSE 调用 SSE&#xff08;Sever-Sent Event&#xff09;&#xff0c;就是浏览器向服务器发送一个HTTP请求&#xff0c;保持长连接&#xff0c;服务器不断单向地向浏览器推送“信息”&#xff08;message&#xff09;&#xff0c;这么做是为了节约网络资源&#xff0c;不用一直…...

智慧校园教学模式的崛起:优化学习体验

在当今数字化时代&#xff0c;智慧校园教学模式正在成为教育界的热门话题。随着科技的不断发展&#xff0c;传统的教学方式已经无法满足现代学生的需求。智慧校园教学模式以其灵活性、互动性和个性化的特点&#xff0c;正逐渐改变着教育的面貌。 首先&#xff0c;智慧校园教学模…...

ffmpeg视频编码原理和实战-(5)对编码过程进行封装并解决丢帧问题

头文件&#xff1a; xencode.h #pragma once #include <mutex> #include<vector> struct AVCodecContext; struct AVPacket; struct AVFrame; class XEncode { public:///// 创建编码上下文/// para codec_id 编码器ID号&#xff0c;对应ffmpeg/// return 编码上…...

halo进阶-主题插件使用

开始捣鼓捣鼓halo&#xff0c;换换主题&#xff0c;加个页面 可参考&#xff1a;Halo 文档 安装/更新主题 主题如同壁纸&#xff0c;萝卜青菜各有所爱&#xff0c;大家按需更换即可&#xff1b; Halo好在一键更换主题&#xff0c;炒鸡方便。 安装/更新插件 此插件还扩展了插件…...

资深开发推荐的IDEA 插件

开发如虎添翼 工欲善其事&#xff0c;必先利其器。想要提升编程开发效率&#xff0c;必须选择一款顺手的开发工具&#xff0c;插件不在多&#xff0c;而在精&#xff0c;作为从业10年的程序员&#xff0c;我目前用到这十几个插件&#xff0c;在平时开发&#xff0c;代码review…...

数学题目系列(一)|丑数|各位和|埃氏筛|欧拉筛

一.丑数 链接&#xff1a;丑数 分析&#xff1a; 丑数只有2&#xff0c;3&#xff0c;5这三个质因数&#xff0c;num 2a 3b 5c也就是一个丑数是由若干个2&#xff0c;3&#xff0c;5组成&#xff0c;那么丑数除以这若干个数字最后一定变为1 代码 class Solution {publi…...

k8s学习--Secret详细解释与应用

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 Secret什么是Secret?Secret四种类型及其特点Secret应用案例&#xff08;1&#xff09;将明文密码进行base64编码&#xff08;2&#xff09;编写创建secret的YAML文…...

功能问题:如何防止接口重复请求?

大家好&#xff0c;我是大澈&#xff01; 本文约 1400 字&#xff0c;整篇阅读约需 3 分钟。 防止接口重复请求在软件开发中非常重要&#xff0c;重复请求必然会导致服务器资源的浪费。 因为每次请求都需要服务器进行处理&#xff0c;如果请求是重复的&#xff0c;那么服务…...

系统架构设计师【第5章】: 软件工程基础知识 (核心总结)

文章目录 5.1 软件工程5.1.1 软件工程定义5.1.2 软件过程模型5.1.3 敏捷模型5.1.4 统一过程模型&#xff08;RUP&#xff09;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() 函数读取数据时&#xff0c;如果返回值小于参数 nmemb 所指定的值&#xff0c;这…...

pESC-HIS是什么,怎么看?-实验操作系列-2

01 典型的pESC-HIS质粒遗传图谱 02 介绍 质粒类型&#xff1a;酿酒酵母蛋白表达载体 表达水平&#xff1a;高拷贝 诱导方法&#xff1a;半乳糖 启动子&#xff1a;GAL1和GAL10 克隆方法&#xff1a;多克隆位点&#xff0c;限制性内切酶 载体大小&#xff1a;6706bp 5 测…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...