当前位置： 首页 > article >正文

【C++】优先队列（Priority Queue）全知道

article 2024/12/2 5:16:14

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

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

 

目录

一、前言

二、优先队列（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】  

 


http://www.kler.cn/a/418017.html

相关文章：

  • STM32的CAN波特率计算
  • LWIP和FATFS 实现 FTP 服务端
  • 【python】图像、音频、视频等文件数据采集
  • Java之链表1
  • 【C语言】二叉树（BinaryTree）的创建、3种递归遍历、3种非递归遍历、结点度的实现
  • 【UE5 C++课程系列笔记】06——定时器的基本使用
  • Spring cache注解：缓存与业务解耦实战
  • 基于51单片机的电子秤设计
  • 网络安全系列 之 SQL注入学习总结
  • 21天掌握Java Web —— 第一天：Spring Boot入门
  • 面积等效原理
  • BUGKU printf
  • Electron builder打包配置
  • Adversarial Learning forSemi-Supervised Semantic Segmentation
  • 第二讲：C++基础语法与程序结构
  • 如何启动 Docker 服务：全面指南
  • python学习笔记8-函数2
  • 引出泛型 实现一个类，类中包含一个数组成员，使得数组中可以存放任何类型的数据，也可以根据成员方法返回数组中某个下标的值？
  • 从零开始学 Maven：简化 Java 项目的构建与管理
  • 数学题转excel；数学题库；数学试卷转excel；大风车excel
  • spring boot如何进行安全测试和渗透测试？
  • 使用ESP32通过Arduino IDE点亮1.8寸TFT显示屏
  • windows下osg程序键盘输入导致程序卡死问题
  • 【天地图】HTML页面实现车辆轨迹、起始点标记和轨迹打点的完整功能
  • windows安装itop
  • 算法刷题Day1