C++中优先队列priority_queue详解(定义、基本用法、常用操作、实例)

在C++标准模板库（STL）中，priority_queue 是一种特殊的容器适配器，用于实现优先级队列。它提供了一种按照特定顺序存储元素的方式，使得每次访问队列时都能获得具有最高优先级的元素。本文将详细介绍 priority_queue 的定义、基本用法、常用操作以及一些实际应用示例，帮助开发者更好地理解和使用这一强大的工具。

一、优先队列 priority_queue 的定义

1. 基本概念

定义：priority_queue 是C++标准模板库中的一个容器适配器，用于实现优先级队列。

头文件：#include <queue>

模板参数：第一个参数：存储的元素类型。

第二个参数：底层容器类型，默认为 vector。

第三个参数：比较函数，默认为 greater（小顶堆）。

1. 功能特点

优先级队列：priority_queue 按照元素的优先级进行排序，每次访问时都会返回具有最高优先级的元素。

动态调整：priority_queue 会自动调整内部元素的顺序，确保每次访问时都能获得具有最高优先级的元素。

支持多种数据类型：priority_queue 可以存储各种数据类型，如整数、浮点数、字符串等。

1. 与其他容器的区别

与 vector 的区别：vector 是一个动态数组，而 priority_queue 是一个基于堆的优先级队列。

与 deque 的区别：deque 是一个双端队列，而 priority_queue 是一个基于堆的优先级队列。

与 list 的区别：list 是一个双向链表，而 priority_queue 是一个基于堆的优先级队列。

二、优先队列 priority_queue 的基本用法

1. 基本声明

示例：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    return 0;
}

解释：上述代码声明了一个存储整数的优先队列 pq。

1. 插入元素

示例：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    pq.push(5);
    pq.push(3);
    pq.push(8);
    return 0;
}

解释：上述代码向优先队列 pq 中插入了三个整数 5、3 和 8。

1. 访问元素

示例：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    pq.push(5);
    pq.push(3);
    pq.push(8);
    cout << "最高优先级元素: " << pq.top() << endl;
    return 0;
}

解释：上述代码访问了优先队列 pq 中的最高优先级元素，并输出其值。

1. 删除元素

示例：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    pq.push(5);
    pq.push(3);
    pq.push(8);
    cout << "最高优先级元素: " << pq.top() << endl;
    pq.pop();
    cout << "删除后最高优先级元素: " << pq.top() << endl;
    return 0;
}

解释：上述代码删除了优先队列 pq 中的最高优先级元素，并输出删除后的最高优先级元素。

1. 清空队列

示例：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    pq.push(5);
    pq.push(3);
    pq.push(8);
    pq.pop();
    pq.pop();
    pq.pop();
    if (pq.empty()) {
        cout << "队列已清空" << endl;
    }
    return 0;
}

解释：上述代码清空了优先队列 pq，并检查是否为空。

三、优先队列 priority_queue 的常用操作

1. 大小

示例：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    pq.push(5);
    pq.push(3);
    pq.push(8);
    cout << "队列大小: " << pq.size() << endl;
    return 0;
}

解释：上述代码获取了优先队列 pq 的大小。

1. 检查是否为空

示例：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    if (pq.empty()) {
        cout << "队列为空" << endl;
    } else {
        cout << "队列不为空" << endl;
    }
    return 0;
}

解释：上述代码检查了优先队列 pq 是否为空。

1. 交换队列

示例：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq1;
    priority_queue<int> pq2;
    pq1.push(5);
    pq1.push(3);
    pq1.push(8);
    pq2.push(1);
    pq2.push(4);
    pq2.push(7);
    pq1.swap(pq2);
    cout << "交换后pq1: ";
    while (!pq1.empty()) {
        cout << pq1.top() << " ";
        pq1.pop();
    }
    cout << endl;
    cout << "交换后pq2: ";
    while (!pq2.empty()) {
        cout << pq2.top() << " ";
        pq2.pop();
    }
    return 0;
}

解释：上述代码交换了两个优先队列 pq1 和 pq2 的内容。

1. 迭代器

示例：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    pq.push(5);
    pq.push(3);
    pq.push(8);
    priority_queue<int> pq_copy = pq;
    cout << "优先队列内容: ";
    while (!pq_copy.empty()) {
        cout << pq_copy.top() << " ";
        pq_copy.pop();
    }
    return 0;
}

解释：上述代码通过迭代器遍历了优先队列 pq 的内容。

四、优先队列 priority_queue 的实例

1. 任务调度

场景：在一个任务调度系统中，需要按照任务的优先级依次执行任务。

示例：

#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct Task {
    string name;
    int priority;
    bool operator<(const Task& other) const {
        return priority < other.priority; // 小顶堆
    }
};
int main() {
    priority_queue<Task> taskQueue;
    taskQueue.push({"Task A", 3});
    taskQueue.push({"Task B", 1});
    taskQueue.push({"Task C", 2});
    while (!taskQueue.empty()) {
        Task currentTask = taskQueue.top();
        taskQueue.pop();
        cout << "执行任务: " << currentTask.name << ", 优先级: " << currentTask.priority << endl;
    }
    return 0;
}

解释：上述代码模拟了一个任务调度系统，按照任务的优先级依次执行任务。

1. 路径规划

场景：在一个路径规划系统中，需要按照路径的距离依次选择路径。

示例：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
    int id;
    double distance;
    bool operator<(const Node& other) const {
        return distance > other.distance; // 小顶堆
    }
};
int main() {
    priority_queue<Node> pathQueue;
    pathQueue.push({1, 10.5});
    pathQueue.push({2, 5.2});
    pathQueue.push({3, 8.9});
    while (!pathQueue.empty()) {
        Node currentNode = pathQueue.top();
        pathQueue.pop();
        cout << "选择路径: " << currentNode.id << ", 距离: " << currentNode.distance << endl;
    }
    return 0;
}

解释：上述代码模拟了一个路径规划系统，按照路径的距离依次选择路径。

1. 事件处理

场景：在一个事件处理系统中，需要按照事件的时间戳依次处理事件。

示例：

#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct Event {
    string name;
    int timestamp;
    bool operator<(const Event& other) const {
        return timestamp < other.timestamp; // 小顶堆
    }
};
int main() {
    priority_queue<Event> eventQueue;
    eventQueue.push({"Event A", 3});
    eventQueue.push({"Event B", 1});
    eventQueue.push({"Event C", 2});
    while (!eventQueue.empty()) {
        Event currentEvent = eventQueue.top();
        eventQueue.pop();
        cout << "处理事件: " << currentEvent.name << ", 时间戳: " << currentEvent.timestamp << endl;
    }
    return 0;
}

解释：上述代码模拟了一个事件处理系统，按照事件的时间戳依次处理事件。

priority_queue 是C++标准模板库中的一个重要工具，用于实现优先级队列。本文详细介绍了 priority_queue 的定义、基本用法、常用操作以及一些实际应用示例。通过本文的介绍，开发者可以更好地理解和应用 priority_queue，提高C++编程的效率和准确性。希望本文提供的信息能够帮助开发者更好地掌握 priority_queue 的使用技巧，避免在实际开发中遇到问题。

声明：所有来源为“聚合数据”的内容信息，未经本网许可，不得转载！如对内容有异议或投诉，请与我们联系。邮箱：marketing@think-land.com