【C++篇】排队的艺术:用生活场景讲解优先级队列的实现

文章目录

须知

💬 欢迎讨论:如果你在学习过程中有任何问题或想法,欢迎在评论区留言,我们一起交流学习。你的支持是我继续创作的动力!

👍 点赞、收藏与分享:觉得这篇文章对你有帮助吗?别忘了点赞、收藏并分享给更多的小伙伴哦!你们的支持是我不断进步的动力!
🚀 分享给更多人:如果你觉得这篇文章对你有帮助,欢迎分享给更多对C++感兴趣的朋友,让我们一起进步!

深入理解与实现:C++优先级队列的模拟实现

1. 引言

在算法和数据结构中,优先级队列是一种极其重要的工具,用于按优先级而非插入顺序处理数据。在C++中,std::priority_queue提供了强大的内置支持,但了解其原理和实现有助于我们更灵活地应用这一数据结构。本文将带你从基础概念出发,逐步实现一个C++版本的优先级队列,并解析其核心原理。

2. 什么是优先级队列?

优先级队列是特殊的队列数据结构,其中每个元素都带有一个优先级,队列的处理顺序依据优先级而定,而不是入队顺序。常见特性包括:

  • 优先级定义:通常用数值表示,数值越大或越小(取决于实现)表示优先级越高。
  • 操作支持:支持插入、删除优先级最高元素。
2.1 现实生活的比喻

在机场登机时,头等舱乘客拥有更高的优先级,会优先登机;在银行排队时,VIP客户的业务会优先处理。优先级队列以数据结构的方式抽象和实现了这些规则。


3. 优先级队列的实现方式

优先级队列的底层通常基于堆结构(Heap)。堆是一种二叉树,分为最大堆和最小堆:

  • 最大堆:根节点是最大值,每个子节点的值都小于或等于父节点。
  • 最小堆:根节点是最小值,每个子节点的值都大于或等于父节点。
3.1 常见实现方法
  • 基于数组或链表:通过手动排序实现,但效率低下。
  • 基于二叉堆:常见且高效,插入和删除的时间复杂度为O(log n)。
  • C++ STL中的实现std::priority_queue利用堆的机制实现优先级队列。

4. 用C++实现优先级队列

接下来,我们将通过代码逐步构建一个优先级队列。

4.1 手动实现优先级队列(基于最大堆)
#include <iostream>
#include <vector>
#include <stdexcept>class PriorityQueue {
private:std::vector<int> heap;void siftUp(int index) {int parent = (index - 1) / 2;if (index > 0 && heap[index] > heap[parent]) {std::swap(heap[index], heap[parent]);siftUp(parent);}}void siftDown(int index) {int left = 2 * index + 1;int right = 2 * index + 2;int largest = index;if (left < heap.size() && heap[left] > heap[largest])largest = left;if (right < heap.size() && heap[right] > heap[largest])largest = right;if (largest != index) {std::swap(heap[index], heap[largest]);siftDown(largest);}}public:void push(int value) {heap.push_back(value);siftUp(heap.size() - 1);}int pop() {if (heap.empty()) {throw std::runtime_error("Priority queue is empty");}int top = heap[0];heap[0] = heap.back();heap.pop_back();if (!heap.empty()) {siftDown(0);}return top;}bool empty() const {return heap.empty();}int top() const {if (heap.empty()) {throw std::runtime_error("Priority queue is empty");}return heap[0];}
};int main() {PriorityQueue pq;pq.push(10);pq.push(20);pq.push(5);std::cout << "Top element: " << pq.top() << std::endl; // 输出 20std::cout << "Popped element: " << pq.pop() << std::endl; // 输出 20std::cout << "Popped element: " << pq.pop() << std::endl; // 输出 10return 0;
}
4.2 使用C++标准库实现优先级队列

C++ STL 提供了内置的优先级队列std::priority_queue,使用起来非常方便。

#include <iostream>
#include <queue>
#include <vector>int main() {// 默认是最大堆std::priority_queue<int> pq;// 插入元素pq.push(10);pq.push(20);pq.push(5);// 查看和删除堆顶元素std::cout << "Top element: " << pq.top() << std::endl; // 输出 20pq.pop();std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 10// 最小堆的实现std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;minHeap.push(10);minHeap.push(20);minHeap.push(5);std::cout << "Top element of minHeap: " << minHeap.top() << std::endl; // 输出 5return 0;
}
5. 优先级队列的应用场景

优先级队列在许多场景中有着广泛的应用:

  1. 任务调度:操作系统为任务分配资源时,根据任务的优先级进行处理。
  2. 最短路径算法:如Dijkstra和A*算法,利用优先级队列动态选择路径。
  3. 数据流处理:实时系统中,优先级队列保证关键数据优先处理。

6. 总结

通过本文的介绍,我们从理论到代码,详细解析了优先级队列的实现与应用。手动实现的优先级队列让我们理解了堆的原理,而C++ STL的std::priority_queue提供了高度优化的工具,便于快速开发。掌握优先级队列不仅能提高算法效率,也能帮助我们更灵活地解决实际问题。

7. 延伸阅读
  • C++ STL 中的堆算法:std::make_heapstd::push_heapstd::pop_heap
  • 二叉堆与平衡树的比较
  • 优先级队列的内存优化技术

通过这篇博客,读者将能够深入理解优先级队列的设计思路和实现方法,并学会在实际开发中灵活运用C++的标准工具,提升程序效率和代码质量。

路虽远,行则将至;事虽难,做则必成

下篇文章再会!!! 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/478328.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

微信小程序+Vant-自定义选择器组件(多选

实现效果 无筛选&#xff0c;如有需要可参照单选组件中的方法.json文件配置"component": true,columns需要处理成含dictLabel和dictValue字段&#xff0c;我是这样处理的&#xff1a; let list arr.map(r > {return {...r,dictValue: r.xxxId,dictLabel: r.xxx…

.NET Core发布网站报错 HTTP Error 500.31

报错如图&#xff1a; 解决办法&#xff1a; 打开任务管理器》》服务》》找到这仨服务&#xff0c;右键启动即可&#xff0c;如果已经启动了就重启&#xff1a;

Canvas 前端艺术家

目前各种数据来看&#xff0c;前端未来在 数据可视化 和 AI 这两个领域会比较香&#xff0c;而 Canvas 是 数据可视化 在前端方面的基础技术。所以给大家唠唠Canvas这个魔幻工具。 Canvas 介绍 Canvas 中文名叫 “画布”&#xff0c;是 HTML5 新增的一个标签。Canvas 允许开发…

Leetcode142. 环形链表 II(HOT100)

链接 我的错误代码&#xff1a; class Solution { public:ListNode *detectCycle(ListNode *head) {if(!head||!head->next)return nullptr;ListNode* f head->next,*s head;while(f){f f->next,s s->next;if(!f)return nullptr;f f->next;if(fs){ListNo…

centos安装小火车

平时没事闲着 装个小火车玩-------->>>>> yum install sl.x86_64 启动命令 sl 就会出现以下场景

JavaScript的let、var、const

这张图片主要介绍了JavaScript中的三种变量声明方式&#xff1a;let、var和const。 1. let 含义&#xff1a;let是现在实际开发中常用的变量声明方式。特点&#xff1a; 块级作用域&#xff1a;let声明的变量只在其所在的块级作用域内有效。例如&#xff1a;{let x 10; } co…

替换Nacos的MySQL驱动

前言&#xff1a;替换Nacos的MySQL驱动能实现使Nacos支持MySQL8.0及以上版本的MySQL数据库 注&#xff1a;下述教程会使用命令先解压Nacos的jar包然后重新用命令把Nacos压缩成jar包&#xff0c;不然直接用压缩工具替换MySQL驱动后的Nacos是会启动不起来的&#xff08;因为没有替…

蓝桥杯每日真题 - 第21天

题目&#xff1a;(空间) 题目描述&#xff08;12届 C&C B组A题&#xff09; 解题思路&#xff1a; 转换单位&#xff1a; 内存总大小为 256MB&#xff0c;换算为字节&#xff1a; 25610241024268,435,456字节 计算每个整数占用空间&#xff1a; 每个 32 位整数占用…

AI赋能电商:构建高效、智能化的新零售生态

随着人工智能&#xff08;AI&#xff09;技术的不断进步&#xff0c;其在电商领域的应用日益广泛&#xff0c;从购物推荐到供应链管理&#xff0c;再到商品定价&#xff0c;AI正在全面改变传统电商的运营模式&#xff0c;并推动行业向智能化和精细化方向发展。本文将探讨如何利…

Python酷库之旅-第三方库Pandas(237)

目录 一、用法精讲 1116、pandas.tseries.offsets.BusinessHour.is_year_end方法 1116-1、语法 1116-2、参数 1116-3、功能 1116-4、返回值 1116-5、说明 1116-6、用法 1116-6-1、数据准备 1116-6-2、代码示例 1116-6-3、结果输出 1117、pandas.tseries.offsets.Cu…

不一样的css(三)

目录 一、前言 二、五角星 1.五角星&#xff0c;叠盖法&#xff1a; 2.五角星&#xff0c;拼凑法&#xff1a; 3.五角星&#xff0c;svg画法&#xff1a; 4.五角星&#xff0c;利用clip-path属性进行裁剪 三、结束语 一、前言 通过上两节的内容我们对css画小图标有了新…

autogen框架中使用chatglm4模型实现react

本文将介绍如何使用使用chatglm4实现react&#xff0c;利用环境变量、Tavily API和ReAct代理模式来回答用户提出的问题。 环境变量 首先&#xff0c;我们需要加载环境变量。这可以通过使用dotenv库来实现。 from dotenv import load_dotenv_ load_dotenv()注意.env文件处于…

Neural Magic 发布 LLM Compressor:提升大模型推理效率的新工具

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

LabVIEW实现TCP/IP通信

目录 1、TCP通信原理 2、硬件环境部署 3、云端环境部署 4、TCP通信函数 5、程序架构 6、前面板设计 7、程序框图设计 8、测试验证 本专栏以LabVIEW为开发平台&#xff0c;讲解物联网通信组网原理与开发方法&#xff0c;覆盖RS232、TCP、MQTT、蓝牙、Wi-Fi、NB-IoT等协议。 结合…

Linux系统Docker部署开源在线协作笔记Trilium Notes与远程访问详细教程

目录 ⛳️推荐 前言 1. 安装docker与docker-compose 2. 启动容器运行镜像 3. 本地访问测试 4.安装内网穿透 5. 创建公网地址 6. 创建固定公网地址 ⛳️推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下…

Linux关于vim的笔记

Linux关于vim的笔记&#xff1a;(vimtutor打开vim 教程) --------------------------------------------------------------------------------------------------------------------------------- 1. 光标在屏幕文本中的移动既可以用箭头键&#xff0c;也可以使用 hjkl 字母键…

Swift 实现链表重新排列:L0 → Ln → L1 → Ln-1

前言 本题由于没有合适答案为以往遗留问题&#xff0c;最近有时间将以往遗留问题一一完善。 143. 重排链表 不积跬步&#xff0c;无以至千里&#xff1b;不积小流&#xff0c;无以成江海&#xff0c;Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言&#xff0c;我们会…

C++ —— 以真我之名 如飞花般绚丽 - 智能指针

目录 1. RAII和智能指针的设计思路 2. C标准库智能指针的使用 2.1 auto_ptr 2.2 unique_ptr 2.3 简单模拟实现auto_ptr和unique_ptr的核心功能 2.4 shared_ptr 2.4.1 make_shared 2.5 weak_ptr 2.6 shared_ptr的缺陷&#xff1a;循环引用问题 3. shared_ptr 和 unique_…

Macos远程连接Linux桌面教程;Ubuntu配置远程桌面;Mac端远程登陆Linux桌面;可能出现的问题

文章目录 1. Ubuntu配置远程桌面2. Mac端远程登陆Linux桌面3. 可能出现的问题1.您用来登录计算机的密码与登录密钥环里的密码不再匹配2. 找不到org->gnome->desktop->remote-access 1. Ubuntu配置远程桌面 打开设置->共享->屏幕共享。勾选允许连接控制屏幕&…

ElasticSearch学习了解笔记

搜索引擎的原理&#xff1a; 1、查询分析&#xff08;自然语言处理&#xff09;理解用户需求 2、分词技术 3、关键词搜索匹配 4、搜索排序 lucence Lucene 是一个成熟的权威检索库 Elasticsearch 的搜索原理简单过程是&#xff0c;索引系统通过扫描文章中的每一个词&#xff…