【C++】优先队列(Priority Queue)全知道

亲爱的读者朋友们😃,此文开启知识盛宴与思想碰撞🎉。

快来参与讨论💬,点赞👍、收藏⭐、分享📤,共创活力社区。

 


目录

一、前言

二、优先队列(Priority Queue):排队也有 “特权”?

(一)优先队列是啥?

(二)C++ 里怎么用优先队列?

(三)优先队列内部到底咋回事?

1. 秘密武器:二叉堆(Binary Heap)

2. 元素进出的 “魔法”

插入(push)元素

删除(pop)元素

(四)优先队列都在哪里大显身手?

1. 任务调度:谁先谁后安排好

2. 图算法中的 “指路明灯”

3. 数据压缩:让数据 “瘦身” 有妙招


一、前言

在 C++ 编程的奇妙世界里,数据结构就像是一个个功能各异的工具,帮助我们高效地处理和组织数据。而在众多的数据结构中,优先队列(Priority Queue)有着独特且重要的地位。它们各自有着独特的工作方式和应用场景,就如同特殊的钥匙,能为我们开启解决不同编程难题的大门。

👉 priority_queue文档介绍 


二、优先队列(Priority Queue):排队也有 “特权”?

(一)优先队列是啥?

想象一下,你在一个超级特别的队伍里。这个队伍里的人可不是按照先来后到排队的哦😉,而是每个人都有一个 “重要程度” 的标签🧾。比如说,在医院的急诊室,重伤的病人就比轻伤的病人更 “重要”,会优先得到救治。这就是优先队列的基本概念啦!它是一种数据结构,元素们按照自己的优先级排队,优先级最高的元素总是站在队伍的最前面,等着被处理。

(二)C++ 里怎么用优先队列?

  1. 标准模板库(STL)来帮忙
    C++ 的 STL 给我们提供了一个超方便的priority_queue类。要用它的话,先把<queue>头文件包含进来哦🧐。就像这样:
    #include <iostream>
    #include <queue>
    
    int main() {
        std::priority_queue<int> pq;
        pq.push(5);
        pq.push(10);
        pq.push(3);
    
        std::cout << "队首元素(最大值): " << pq.top() << std::endl;
    
        pq.pop();
    
        std::cout << "队首元素(最大值): " << pq.top() << std::endl;
    
        return 0;
    }

    这里我们创建了一个存整数的优先队列,默认情况下,它就像一个 “选大比赛”,最大的数在队首哦😎。每次push进去一个数,它就会自动按照大小排好队,top就能看到队首的最大值,pop就把最大值请出去啦。

  2.  想自定义规则?没问题!
    要是你觉得默认的 “选大” 或者 “选小” 规则不合心意,也可以自己定规则哦😏。这时候就要用到比较函数或者函数对象啦。看下面这个例子,我们来创建一个小顶堆,让最小的数在队首

    #include <iostream>
    #include <queue>
    
    struct Compare {
        bool operator()(int a, int b) {
            return a > b;
        }
    };
    
    int main() {
        std::priority_queue<int, std::vector<int>, Compare> pq;
        pq.push(5);
        pq.push(10);
        pq.push(3);
    
        std::cout << "队首元素(最小值): " << pq.top() << std::endl;
    
        pq.pop();
    
        std::cout << "队首元素(最小值): " << pq.top() << std::endl;
    
        return 0;
    }

    我们定义了一个Compare结构体,里面的operator()函数就是我们的比较规则。这样,优先队列就会按照我们定的规则来排队啦。

 

(三)优先队列内部到底咋回事?

1. 秘密武器:二叉堆(Binary Heap)

其实呀,priority_queue背后是靠二叉堆这个小助手来干活的呢😎。二叉堆就像一棵特别的树,每个节点都有自己的任务哦。对于大顶堆来说,父节点就像个小队长,它的值得比子节点的值大,这样才能保证队里最大的值在最上面呀。小顶堆呢,就刚好相反,父节点的值要小于等于子节点的值。

 下面是个简单示意二叉堆节点结构体的代码,实际 STL 里的实现更复杂哦:

template<typename T>
struct BinaryHeapNode {
    T value;
    BinaryHeapNode<T>* left;
    BinaryHeapNode<T>* right;

    BinaryHeapNode(T val) : value(val), left(nullptr), right(nullptr) {}
};
2. 元素进出的 “魔法”
插入(push)元素

当有新元素要加进这个特别的队伍时,它会先站到队伍最后面哦。然后呢,它就开始和前面的人比,如果它比前面的人更 “重要”(按堆的规则),就和前面的人换位置,一直这么比下去,直到找到自己合适的位置,这就叫 “上溯(sift up)” 啦,就好像新队员要在队伍里找到自己的等级一样呢🧐。

下面是个简单示例代码片段,展示插入元素并维护二叉堆性质(假设已有上面那个二叉堆节点结构体定义哦):

template<typename T>
void siftUp(BinaryHeapNode<T>* node) {
    while (node!= nullptr && node->parent!= nullptr && node->value > node->parent->value) {
        // 交换节点和其父节点的值
        swap(node->value, node->parent->value);
        node = node->parent;
    }
}

template<typename T>
void pushToHeap(BinaryHeapNode<T>* root, T value) {
    // 创建新节点并插入到堆的末尾
    BinaryHeapNode<T>* newNode = new BinaryHeapNode<T>(value);
    if (root == nullptr) {
        root = newNode;
    } else {
        // 找到合适的位置插入新节点(这里简单假设插入到最后一个叶子节点位置)
        BinaryHeapNode<T>* current = root;
        while (current->left!= nullptr && current->right!= nullptr) {
            current = current->left;
        }
        if (current->left == nullptr) {
            current->left = newNode;
        } else {
            current->right = newNode;
        }

        // 对新插入的节点进行上溯操作
        siftUp(newNode);
    }
}
删除(pop)元素

当要处理队首元素(也就是pop操作)时,队伍最后面的那个人会跑到队首来。但他可能不符合队首的要求呀,所以他就得和下面的人比,如果下面的人比他更 “适合” 队首,就和下面的人换位置,一直比到他找到自己合适的位置为止,这就是 “下溯(sift down)” 的过程啦😉。

 下面是个简单示例代码片段,展示删除堆顶元素并维护二叉堆性质(同样假设已有上面那个二叉堆节点结构体定义哦):

template<typename T>
void siftDown(BinaryHeapNode<T>* node) {
    while (node!= nullptr) {
        BinaryHeapNode<T>* largest = node;
        if (node->left!= nullptr && node->left->value > largest->value) {
            largest = node->left;
        }
        if (node->right!= nullptr && node->right->value > largest->value) {
            largest = node->right;
        }
        if (largest!= node) {
            // 交换节点和最大子节点的值
            swap(node->value, largest->value);
            node = largest;
        } else {
            break;
        }
    }
}

template<typename T>
T popFromHeap(BinaryHeapNode<T>* root) {
    if (root == nullptr) {
        throw runtime_error("堆为空");
    }

    T rootValue = root->value;
    // 将堆的最后一个节点的值赋给堆顶
    BinaryHeapNode<T>* lastNode = findLastNode(root);
    root->value = lastNode->value;

    // 删除最后一个节点(这里简单假设能正确删除,实际可能更复杂)
    delete lastNode;

    // 对新的堆顶节点进行下溯操作
    siftDown(root);

    return rootValue;
}

在这代码里,popFromHeap函数就是用来删二叉堆的堆顶元素的,删完后用siftDown函数来保证二叉堆还是符合大顶堆的条件呢。

(四)优先队列都在哪里大显身手?

1. 任务调度:谁先谁后安排好

在操作系统或者任务管理系统里呀,任务就像一群等着被处理的小士兵👨‍✈️。每个任务都有自己的优先级,比如紧急任务优先级高,普通任务优先级低。优先队列就像个聪明的指挥官,把任务按优先级排好队,处理器就可以按顺序先处理重要的任务啦,这样系统就能高效地运行咯,就跟快递分拣中心会优先处理加急件一样呢😎。

下面是个简单的任务调度模拟代码示例,用优先队列来实现任务按优先级排序处理哦:

#include <iostream>
#include <queue>
#include <string>

using namespace std;

// 任务结构体
struct Task {
    string name;
    int priority;

    Task(const string& n, int p) : name(n), priority(p) {}
};

// 自定义比较函数,按照任务优先级从高到低排序
struct TaskCompare {
    bool operator()(const Task& t1, const Task& t2) {
        return t1.priority < t2.priority;
    }
};

int main() {
    // 创建任务优先队列
    priority_queue<Task, vector<Task>, TaskCompare> taskQueue;

    // 添加一些任务到队列
    taskQueue.push(Task("任务1", 5));
    taskQueue.push(Task("任务2", 3));
    taskQueue.push(Task("任务3", 8));

    // 模拟处理器处理任务
    while (!taskQueue.empty()) {
        Task currentTask = taskQueue.top();
        cout << "正在处理任务: " << currentTask.name << ",优先级: " << currentTask.priority << endl;
        taskQueue.pop();
    }

    return 0;
}

 

 在这个例子里,我们先定义了Task结构体来表示任务,有任务名字和优先级两个属性哦。然后通过自定义的TaskCompare比较函数,让优先队列按任务优先级从高到低给任务排队。最后模拟处理器依次处理队列里的任务呢。

2. 图算法中的 “指路明灯”

在一些图算法里呀,比如 Dijkstra 算法求单源最短路径,优先队列可真是个大功臣呢🧐。想象一下你在一个迷宫里找出口,每个路口都有不同的距离标记。算法得不断选离起点最近的未访问路口继续探索呀,优先队列就能很快告诉算法哪个路口离起点最近,就像个导航仪一样,让算法能高效地找到最短路径呢😉。

下面是个简单的 Dijkstra 算法示例,用优先队列来辅助找到从一个源点到其他节点的最短路径哦(这只是个简化示例,实际应用可能更复杂啦):

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>

using namespace std;

// 节点结构体
struct Node {
    int id;
    vector<Node*> neighbors;
    int distance;

    Node(int i) : id(i), distance(INT_MAX) {}
};

// 自定义比较函数,按照节点距离从小到大排序
struct NodeCompare {
    bool operator()(const Node* n1, const Node* n2) {
        return n1->distance > n2->distance;
    }
};

// Dijkstra算法实现
void dijkstra(Node* source) {
    // 创建优先队列,按照节点距离排序
    priority_queue<Node*, vector<Node*>, NodeCompare> pq;

    // 将源点加入队列,并设置其距离为0
    source->distance = 0;
    pq.push(source);

    // 用于记录已访问过的节点
    unordered_map<int, bool> visited;

    while (!pq.empty()) {
        Node* currentNode = pq.top();
        pq.pop();

        // 如果节点已经访问过,跳过
        if (visited[currentNode->id]) {
            continue;
        }

        // 标记当前节点为已访问
        visited[currentNode->id] = true;

        // 更新当前节点邻居的距离
        for (Node* neighbor : currentNode->neighbors) {
            int newDistance = currentNode->日前距离 + 1;
            if (newDistance < neighbor->distance) {
                neighbor->distance = newDistance;
                pq.push(neighbor);
            }
        }
    }
}

int main() {
    // 创建一些节点
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);

    // 构建节点之间的连接关系
    node1->日前邻居.push_back(node2);
    node1->日前邻居.push_back(node3);
    node2->日前邻居.push_back(node3);

    // 运行Dijkstra算法
    dijkstra(node1);

    // 输出节点到源点的距离
    cout << "节点2到源点的距离: " << node2->distance << endl;
    cout << "节点3到源点的距离: " << node3->distance << endl;

    return 0;
}

 在这个例子里,我们先定义了Node结构体来表示图中的节点,有节点 ID、邻居节点列表和到源点的距离这些属性哦。然后通过自定义的NodeCompare比较函数,让优先队列按节点距离从小到大给节点排队。接着在 Dijkstra 算法里,利用优先队列高效地选离源点最近的未访问节点进行处理,这样就能找到从源点到其他节点的最短路径啦。

3. 数据压缩:让数据 “瘦身” 有妙招

在哈夫曼编码这个数据压缩方法里呀,优先队列也发挥着重要作用呢😎。它就像个聪明的小助手,帮我们构建哈夫曼树。在构建过程中,它会选出现频率最低的两个字符,把它们合并成一个新的 “组合字符”,然后继续选频率最低的进行合并,直到构建出完整的哈夫曼树。最后根据这棵树给每个字符分配不同长度的编码,这样就能让数据占用更少的空间啦😃。

 下面是个简单的哈夫曼编码构建示例,用优先队列来辅助构建哈夫曼树哦(这也是个简化示例,实际应用可能更复杂啦):

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>

using namespace std;

// 哈夫曼树节点结构体
struct HuffmanNode {
    char data;
    int frequency;
    HuffmanNode* left;
    HuffmanNode* left右;

    HuffmanNode(char d, int f) : data(d), frequency(f), left(nullptr), left右(nullptr) {}
}

// 自定义比较函数,按照节点频率从小到大排序
struct HuffmanNodeCompare {
    bool operator()(const HuffmanNode* n1, const HuffmanNode* n2) {
        return n1->frequency > n2->frequency;
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(const unordered_map<char, int>& frequencyMap) {
    // 创建优先队列,按照节点频率排序
    priority_queue<HuffmanNode*, vector<H夫曼Node*>, HuffmanNodeCompare> pq;

    // 将每个字符及其频率对应的节点加入队列
    for (const auto& pair : frequencyMap) {
        pq.push(new HuffmanNode(pair.first, pair.second));
    }

    while (pq.size() > 1) {
        // 取出频率最低的两个节点
        HuffmanNode* leftNode = pq.top();
        pq.pop();
        HuffmanNode* rightNode = pq.top();
        pq.pop();

        // 创建新的父节点,频率为两个子节点频率之和
        HuffmanNode* parentNode = new HuffmanNode('\0', leftNode->frequency + rightNode->frequency);
        parentNode->left = leftNode;
        parentNode->right = rightNode;

        // 将父节点加入队列
        pq.push(parentNode);
    }

    return pq.top();
}

int main() {
    // 假设这里有个字符频率映射表
    unordered_map<char, int> frequencyMap = {
        {'a', 5},
        {'b', 3},
        {'c', 8}
    };

    // 构建哈夫曼树
    HuffmanNode* huffmanTree = buildHuffmanTree(frequencyMap);

    // 这里可以根据哈夫曼树进一步处理,比如生成编码等,但为了简化先不展示啦

    return 0;
}

 在这个例子里,我们先定义了HuffmanNode结构体来表示哈夫曼树的节点,有字符数据、频率、左右子节点这些属性哦。然后通过自定义的HuffmanNodeCompare比较函数,让优先队列按节点频率从小到大给节点排队。接着在构建哈夫曼树的过程中,利用优先队列选出频率最低的两个节点合并成新节点,一直重复这个过程直到构建出完整的哈夫曼树呢。


如果本文对你有帮助欢迎关注我👉【A Charmer】  

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

服务熔断-熔断器设计

文章目录 服务为什么需要熔断熔断器设计思想熔断器代码实现 服务为什么需要熔断 对于服务端采用的保护机制为服务限流。 对于服务调用端是否存在保护机制&#xff1f; 假如要发布一个服务 B&#xff0c;而服务 B 又依赖服务 C&#xff0c;当一个服务 A 来调用服务 B 时&#x…

新能源汽车智慧充电桩管理方案:应用选型与充电协议应该怎么做?

新能源智慧充电桩平台采用虚拟化技术&#xff0c;使多种应用共享服务器、存储等硬件资源&#xff0c;可以帮助用户提供IT基础设施资源的利用效率&#xff0c;提升基础设施的应用和管理水平&#xff0c;实现计算资源的动态优化&#xff0c;使平台应用易维护、易扩充。 1、行业背…

SickOs: 1.1靶场学习小记

学习环境 kali攻击机&#xff1a;Get Kali | Kali Linux vulnhub靶场&#xff1a;https://download.vulnhub.com/sickos/sick0s1.1.7z 靶场描述&#xff1a; 这次夺旗赛清晰地模拟了在安全环境下如何对网络实施黑客策略从而入侵网络的过程。这个虚拟机与我在进攻性安全认证专…

[极客大挑战 2019]PHP--详细解析

信息搜集 想查看页面源代码&#xff0c;但是右键没有这个选项。 我们可以ctrlu或者在url前面加view-source:查看&#xff1a; 没什么有用信息。根据页面的hint&#xff0c;我们考虑扫一下目录看看能不能扫出一些文件. 扫到了备份文件www.zip&#xff0c;解压一下查看网站源代码…

python学习笔记 - python安装与环境变量配置

目录 前言1. 版本选择1.1 什么版本合适&#xff1f;1.2 版本越新越好吗&#xff1f;1.3 维护中的大版本里&#xff0c;选择最早的好吗&#xff1f;1.4 我的选择1.5 Python 发布周期1.6 Python维护中的版本及截止时间 2. 安装包下载2.1 官网地址2.2 下载安装包3. 环境安装3.1 新…

[Linux] 进程间通信——匿名管道命名管道

标题&#xff1a;[Linux] 进程间通信——匿名管道&&命名管道 水墨不写bug &#xff08;图片来源于网络&#xff09; 目录 一、进程间通信 二、进程间通信的方案——匿名管道 &#xff08;1&#xff09;匿名管道的原理 &#xff08;2&#xff09;使用匿名管道 三、进…

uniapp在App端定义全局弹窗,当打开关闭弹窗会触发onShow、onHide生命周期怎么解决?

在uniapp(App端)中实现自定义弹框&#xff0c;可以通过创建一个透明页面来实现。点击进入当前页面时&#xff0c;页面背景会变透明&#xff0c;用户可以根据自己的需求进行自定义&#xff0c;最终效果类似于弹框。 遇到问题&#xff1a;当打开弹窗(进入弹窗页面)就会触发当前页…

Linux之信号的产生,保存,捕捉

Linux之信号的产生&#xff0c;保存&#xff0c;捕捉处理 一.信号的概念1.1概念1.2分类 二.信号的产生2.1通过键盘产生的信号2.2系统调用接口产生的信号2.3硬件异常产生的信号2.4软件条件产生的信号 三.信号的保存四.信号的捕捉五.信号的其他杂碎知识5.1可重入函数5.2volatile关…

快排详解(4种写法:霍尔/挖坑法/双指针/非递归)

//本文所写快排的结果都是从小到大排序 思路 快排就是把数组的第一个值记为key,然后定义两个指针,一个叫begin,一个叫end. begin指针从数组的头部出发,寻找比key大的值;end指针从数组的尾部出发,寻找比key小的值; 然后交换begin和end的值 ......最后,begin和end相遇就停下…

Linux服务器安装mongodb

因为项目需要做评论功能&#xff0c;领导要求使用mongodb&#xff0c;所以趁机多学习一下。 在服务器我们使用docker安装mongodb 1、拉取mongodb镜像 docker pull mongo &#xff08;默认拉取最新的镜像&#xff09; 如果你想指定版本可以这样 docker pull mongo:4.4&#…

Bert+CRF的NER实战

CRF&#xff08;条件随机场-Conditional Random Field&#xff09; 原始本文&#xff1a;我在北京吃炸酱面 标注示例&#xff1a; 我O在O北B-PLA京I-PLA吃O炸B-FOOD酱I-FOOD面I-FOOD CRF&#xff1a; 目的&#xff1a;提出一些不可能出现的预测组合&#xff08;例如I-PLA不能…

时序论文27|Fredformer:频域去偏差的时序预测Transformer模型

论文标题&#xff1a;Fredformer: Frequency Debiased Transformer for Time Series Forecasting 论文链接&#xff1a;https://arxiv.org/abs/2406.09009 代码链接&#xff1a;https://github.com/chenzRG/Fredformer 前言 这篇文章发表于KDD2024&#xff0c;作者的出发点…

带外配置IP

要想了解带内&#xff0c;私下我 管理IP:9.101.8.20 掩码&#xff1a;255.0.0.0 网关&#xff1a;9.101.0.254 1 首先自己电脑要修改ip 192.168.70.x 段 2 在cmd 去ping 192.168.70.125 必须通 3 去浏览器 登录192.168.70.125 4 更改ip 5 再次修改电脑IP 网关 掩码 7 检测…

大型复杂项目管理怎么结合传统与敏捷

大型复杂项目管理需要综合运用传统的瀑布模型与敏捷方法&#xff0c;两者各具优势&#xff0c;可以在不同的项目阶段和需求下发挥最大效能。首先&#xff0c;在项目的初期阶段&#xff0c;传统方法的详细规划和需求分析能够帮助确保项目方向正确、资源充足&#xff1b;敏捷方法…

Vue 2.0->3.0学习笔记(Vue 3 (四)- Composition API 的优势)

Vue 2.0-&#xff1e;3.0学习笔记&#xff08;Vue 3 &#xff08;四&#xff09;- Composition API 的优势&#xff09; Composition API 的优势1. Options API 存在的问题2. Composition API 的优势 Composition API 的优势 1. Options API 存在的问题 笔记 使用传统OptionsA…

工程设计与总承包行业数字化转型:现状洞察、挑战突围与前景展望

一、现状洞察 &#xff08;一&#xff09;数字化技术应用初现成效 BIM 技术局部应用&#xff1a;部分企业在工程设计阶段利用 BIM 技术实现三维建模和设计可视化&#xff0c;施工前模拟环节可优化流程提高效率&#xff0c;但普及程度有待提高。项目管理软件逐步推广&#xff…

Spring Boot优雅读取配置信息 @EnableConfigurationProperties

很多时候我们需要将一些常用的配置信息比如oss等相关配置信息放到配置文件中。常用的有以下几种&#xff0c;相信大家比较熟悉&#xff1a; 1、Value(“${property}”) 读取比较简单的配置信息&#xff1a; 2、ConfigurationProperties(prefix “property”)读取配置信息并与 …

关于音频 DSP 的接口种类以及其应用场景介绍

在音频系统中&#xff0c;DSP&#xff08;数字信号处理器&#xff09;扮演着重要角色&#xff0c;通常会通过不同的接口与音频系统中的其他组件&#xff08;如功放、扬声器、音频源等&#xff09;进行连接。以汽车应用场景为例&#xff0c;以下是一些常见的接口类型分类及其介绍…

A02、数据库性能调优

1、如何写出高性能SQL语句 1.1、慢SQL原因 1.1.1、无索引、索引失效导致慢查询 如果在一张几千万数据的表中以一个没有索引的列作为查询条件&#xff0c;大部分情况下查询会非常耗时&#xff0c;这种查询毫无疑问是一个慢 SQL 查询。所以对于大数据量的查询&#xff0c;我们需…

基于FPGA的FM调制(载波频率、频偏、峰值、DAC输出)-带仿真文件-上板验证正确

基于FPGA的FM调制-带仿真文件-上板验证正确 前言一、FM调制储备知识载波频率频偏峰值个人理解 二、代码分析1.模块分析2.波形分析 总结 前言 FM、AM等调制是学习FPGA信号处理一个比较好的小项目&#xff0c;通过学习FM调制过程熟悉信号处理的一个简单流程&#xff0c;进而熟悉…