Priority_Queue 的使用和模拟

2024-08-30 02:44
文章标签 使用 模拟 queue priority

本文主要是介绍Priority_Queue 的使用和模拟,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录
一·基本的介绍

优先队列是一种容器适配器;他的第一个元素总是他包含所有元素里面最大的一个

他的底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。
这个底层容器应该可以通过随机访问迭 代器,并支持以下操作:
empty():检测容器是否为空
size():返回容器中有效元素个数
front():返回容器中第一个元素的引用
push_back():在容器尾部插入元素
pop_back():删除容器尾部元素

优先队列里面的“优先”指的是:进行容器遍历访问 的时候优先访问顶部的元素

二. 常用接口的介绍 
1.构造函数

2. void push(const T&val ) 

3. void pop()

 4. const T& top( )

 

 接口的简单使用:

 通过对成员接口的了解,我们可以推测优先队列的底层结构可能是一个

三· 模拟实现
1.仿函数

第一个参数用到的就是仿函数。

仿函数是对 opertaor() 的一个重载

2.仿函数使用
2.1  指定进行降序的输出
2.2 指定进行升序的输出 

2.3 仿函数的调用 

分析:

Less <Date> l2,编译器进行实例化的时候,模板参数T 实例化为 Date 类型,从而生成一份

bool operator() (Date left,Date right)的函数,只不过使用模板,咱们程序员省了此步骤。 

3.priority_queue 类的模拟

一般默认Container 的类型是  vector<T>

为什么默认使用 vector 作为优先队列的底层容器?而不用list这个容器

1) 优先队列支持快速的访问此队列里面的最大或者最小元素;因此底层通常借助堆这一结构实

现,堆是一个特殊的完全二叉树

2)vector 提供了动态大小数组的功能,内部是一段连续的内存,因此在访问元素的时候,大大提

高了效率

3)list 相比较vector 而言,内存是不连续的,在进行元素访问的时候,需要对指针进行一系列操

作,因此效率不如vector

4 push() 模拟

因为需要随时保证访问的第一个元素是最大的或是最小的,这里需模拟建大堆和建小堆的一系列操

有关对堆进行上调和下调的相关细节的实现,可以康康下面博客

 建堆的相关调整

4.1 上调算法
  void adjust_up(int child) //从孩子节点开始{Compare com;int parent = (child - 1 ) / 2;//默认根节点下标从0开始while (child > 0){if (_c[parent] < _c[child]) //对象直接比较//if(com(_c[parent] , _c[child]))  // _com(_c[parent] , _c[child] 相当于回调仿函数模板,可以把_com 想象成函数指针,仿函数模板:替代函数指针{std::swap(_c[parent], _c[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}}
4.2 push ()实现
  void push(const T& x){_c.push_back(x);// 上调:建大堆adjust_up(_c.size()-1);//需要把插入当前数据所在的位置传过去}
5.pop()模拟
5.1 下调算法
        void adjust_down(int parent) //向下调整从父节点开始{Compare com;int child = 2 * parent + 1;while ((size_t)child < (_c.size() )){if ((size_t)child + 1 < (_c.size() ) && _c[child + 1] > _c[child]) // _c[child + 1] > _c[child] 这里直接就是对象的大小比较,可以使用仿函数进行大小比较child++;//更新为最大的孩子节点//if (_c[child] > _c[parent] )if (com( _c[parent], _c[child]) ) //使用仿函数模板{std::swap(_c[child], _c[parent]);parent = child;child = 2 * parent + 1;}elsebreak;}}
5.2 pop()实现
        void pop() {//堆的删除:堆顶与堆尾交换在进行大堆的调整std::swap(_c[0], _c[_c.size() - 1]);_c.pop_back();adjust_down(0);}
6. top()模拟
        T& top(){return _c[0];}
7.size()

8. empty()

9. 完整代码实现 
#pragma once
#include<vector>
namespace y
{//仿函数模板//就是对 () 进行重载template<class T, class Container = vector<T>,class Compare = Less<T>>  //注意:Compare 只是一个模板类型,实例化的时候,会变成指定类型class priority_queue{public:priority_queue(){}template <class InputIterator>priority_queue(InputIterator first, InputIterator last):_c(first,last){//建议使用下调时间复杂度 O(N)//必须是有序,所有一开始传i = (_c.size() - 1 -1)/2 对应最后一个父节点for (int i = (_c.size() - 1 -1)/2; i >= 0; --i){adjust_down(i);}}bool empty() const{return _c.empty();}size_t size() const{return _c.size();}void adjust_down(int parent) //向下调整从父节点开始{Compare com;int child = 2 * parent + 1;while ((size_t)child < (_c.size() )){if ((size_t)child + 1 < (_c.size() ) //&& _c[child + 1] > _c[child]) // _c[child + 1] > _c[child] 这里直接就是对象的大小比较,可以使用仿函数进行大小比较&& com(_c[child], _c[child+1]))// 建大堆child++;//更新为最大的孩子节点//if (_c[child] > _c[parent] )if (com( _c[parent], _c[child]) ) //使用仿函数模板{std::swap(_c[child], _c[parent]);parent = child;child = 2 * parent + 1;}elsebreak;}}void adjust_up(int child) //从孩子节点开始{Compare com;int parent = (child - 1 ) / 2;//默认根节点下标从0开始while (child > 0){//if (_c[parent] < _c[child]) //对象直接比较if(com(_c[parent] , _c[child]))  // _com(_c[parent] , _c[child] 相当于回调仿函数模板,可以把_com 想象成函数指针,仿函数模板:替代函数指针{std::swap(_c[parent], _c[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}}void pop() {//堆的删除:堆顶与堆尾交换在进行大堆的调整std::swap(_c[0], _c[_c.size() - 1]);_c.pop_back();adjust_down(0);}void push(const T& x){_c.push_back(x);// 上调:建大堆adjust_up(_c.size()-1);//需要把插入当前数据所在的位置传过去}T& top(){return _c[0];}private:Container _c;//表示底层的容器//Compare _com;//类似于函数指针};
}

这篇关于Priority_Queue 的使用和模拟的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1119577

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库:创建新文件夹,进入文件夹目录,执行指令 git init ,用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的