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

priority_queue--优先队列

一、认识优先队列

        priority_queue(优先队列)是 C++ 标准模板库(STL)中的一个容器适配器。它的底层实现通常是用(一般是二叉堆)来实现的。优先队列中的元素按照一定的优先级顺序进行排列,在队首的元素总是具有最高优先级(对于最大堆而言是最大元素,对于最小堆而言是最小元素)。

        它就像是一个特殊的队列,普通队列是先进先出(FIFO),而优先队列是按照优先级高低来决定出队的顺序。

二、优先队列的模拟实现

        

#include<iostream>
#include<vector>
#include<deque>using namespace std;
namespace ts
{template<class T, class Container = vector<int>, class Compare = less<T> >class priority_queue{public://向上调整建堆法void AdiustUp(int child){int parent = (child - 1) / 2;while (child > 0){if (_com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}//向下调整建堆法void AdiustDown(int parent){int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _com(_con[child], _con[child + 1])){++child;}if (_com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}priority_queue(){}template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);AdiustUp(_con.size() - 1);++first;}}void push(const T& x){_con.push_back(x);AdiustUp(_con.size() - 1);}bool empty()const{return _con.empty();}const T& top()const{return _con.front();}const size_t size()const{return _con.size();}void pop(){swap(_con[0],_con[_con.size() - 1]);_con.pop_back();AdiustDown(0);}private:Container _con;Compare _com;};
}

http://www.lryc.cn/news/495436.html

相关文章:

  • Paper -- 建筑物高度估计 -- 基于深度学习、图像处理和自动地理空间分析的街景图像建筑高度估算
  • 开发一套ERP 第八弹 RUst 插入数据
  • 回退用 git revert 还是 git reset?
  • 【docker】多阶段构建与基础构建,及企业案例展示
  • 基于链表的基础笔试/面试题
  • SARIMA 模型Matlab代码
  • 第八课 Unity编辑器创建的资源优化_特效篇(Particle System)详解
  • Oracle对比表与表之间的结构
  • 基于JSP+MySQL的网上招聘系统的设计与实现
  • 【Linux】进程地址空间(虚拟地址vs物理地址vs页表)
  • pytorch 融合 fuse 学习笔记
  • 在 Ubuntu 20.04 上使用 Lux 下载 Bilibili 视频的详细教程
  • 【eclipse】快捷键
  • 集成开发环境(IDE)的使用技巧插件配置
  • 【如何提升代码工程质量】code review篇
  • Qt 面试题学习13_2024-12-1
  • Hive 安装与架构详解
  • 前端入门指南:模块打包器是什么?模块打包器的工作原理与实践
  • 初识ProtoBuf以及环境搭建(Win和Ubuntu)
  • springboot366高校物品捐赠管理系统(论文+源码)_kaic
  • 【Python网络爬虫笔记】5-(Request 带参数的get请求) 爬取豆瓣电影排行信息
  • 递归算法讲解(c基础)
  • AJAX一、axios使用,url组成(协议,域名,资源路径)查询参数和化简,错误处理,请求/响应报文,状态码,接口文档,
  • QT6学习第六天 初识QML
  • 映射vim键位,基本功能键位表(未更完)
  • Python学习笔记(5)Python的创建型设计模式
  • qt QAnimationDriver详解
  • 零拷贝相关知识点(一)
  • STM32的CAN波特率计算
  • 简单好用的折线图绘制!