异常教程

C++ 容器类 <priority_queue>（一文讲透）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

  • 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
  • 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

前言

在 C++ 标准库中，容器类 <priority_queue> 是一个功能强大且应用广泛的工具。它通过优先级机制对数据进行排序和管理，适用于需要快速访问最大值或最小值的场景。无论是实现任务调度、路径寻找算法，还是处理实时数据流，<priority_queue> 都能提供高效的解决方案。本文将从基础概念、实现原理到实际应用，逐步解析这一容器类的核心特性，并通过代码示例帮助读者掌握其使用方法。

基本概念与核心特性

什么是优先队列？

优先队列（Priority Queue）是一种特殊的队列结构，其元素按照优先级排序。与普通队列（先进先出，FIFO）不同，优先队列中优先级最高的元素总会被最先取出。

  • 优先级规则：可以是默认的最大堆（最大值优先）或最小堆（最小值优先）。
  • 动态性：支持频繁的插入和删除操作，且时间复杂度较低。

形象比喻：
想象一个快递分拣中心，包裹按紧急程度分类。优先队列就像一个智能分拣系统，总是先处理标有“紧急”的包裹，而普通包裹则按顺序等待。

标准库 <priority_queue> 的特点

在 C++ 中，<priority_queue> 是 <queue> 头文件中的模板类，其底层通常基于**堆（Heap）**结构实现。以下是其核心特性：

  1. 默认最大堆：若不指定比较函数，默认按元素大小构建最大堆，最大值位于队列顶部。
  2. 不可直接访问元素：无法随机访问元素，仅支持 push()、pop()、top() 和 empty() 等接口。
  3. 灵活的自定义排序：通过传递自定义比较函数（如 lambda 表达式或仿函数），可实现最小堆或其他排序逻辑。

快速入门：基础用法与代码示例

最小配置：默认最大堆

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> max_heap;
    max_heap.push(10); // 插入元素
    max_heap.push(5);
    max_heap.push(15);
    
    std::cout << "Top element: " << max_heap.top() << std::endl; // 输出 15
    max_heap.pop(); // 移除最大值
    std::cout << "New top after pop: " << max_heap.top() << std::endl; // 输出 10
    
    return 0;
}

关键点解释：

  • push() 将元素按优先级插入堆中。
  • top() 返回堆顶元素（最大值）。
  • pop() 移除堆顶元素，并重新调整堆结构以维持优先级。

自定义比较函数：实现最小堆

若需要最小堆，可通过重载比较运算符或传递仿函数实现：

#include <queue>
#include <vector>
#include <functional>

int main() {
    // 方法一：使用 std::greater 定义最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(10);
    min_heap.push(5);
    min_heap.push(15);
    std::cout << "Min-heap top: " << min_heap.top() << std::endl; // 输出 5
    
    // 方法二：自定义仿函数（类）
    struct Compare {
        bool operator()(const int& a, const int& b) {
            return a > b; // 小顶堆逻辑
        }
    };
    std::priority_queue<int, std::vector<int>, Compare> custom_heap;
    custom_heap.push(20);
    custom_heap.push(3);
    std::cout << "Custom compare top: " << custom_heap.top() << std::endl; // 输出 3
    
    return 0;
}

深入原理：堆结构与实现机制

堆的底层实现

<priority_queue> 的底层通常基于二叉堆（Binary Heap），分为两种类型：

  1. 最大堆（Max-Heap）：父节点的值大于等于子节点。
  2. 最小堆（Min-Heap）：父节点的值小于等于子节点。

数组模拟堆的索引规则：
假设堆以数组形式存储，元素 i 的左右子节点分别为 2*i + 1 和 2*i + 2，父节点为 (i-1)/2。

堆的调整操作：

  • 上浮（Sift Up）：当新元素插入时，若其值比父节点大（最大堆），则交换位置，直到堆序被恢复。
  • 下沉（Sift Down）：当堆顶元素被移除后，最后一个元素填补堆顶，再逐层比较并下沉到合适位置。

时间复杂度分析

操作时间复杂度说明
push()O(log n)需上浮调整堆结构
pop()O(log n)移除堆顶并下沉调整
top()O(1)直接访问堆顶元素
empty()O(1)检查队列是否为空
size()O(1)返回当前元素数量（需手动实现）

实战案例：应用场景与代码实现

案例一：Dijkstra 算法中的最短路径

在图论中，Dijkstra 算法常通过优先队列优化单源最短路径问题。优先队列按距离排序，每次取出当前距离最小的节点进行扩展：

#include <queue>
#include <vector>
#include <climits>

struct Node {
    int vertex;
    int distance;
    bool operator>(const Node& other) const {
        return distance > other.distance; // 小顶堆比较
    }
};

void dijkstra(int start, std::vector<std::vector<int>>& graph) {
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> pq;
    std::vector<int> dist(graph.size(), INT_MAX);
    
    dist[start] = 0;
    pq.push({start, 0});
    
    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        
        if (current.distance > dist[current.vertex]) continue;
        
        for (int neighbor = 0; neighbor < graph.size(); ++neighbor) {
            if (graph[current.vertex][neighbor] != -1) {
                int new_dist = dist[current.vertex] + graph[current.vertex][neighbor];
                if (new_dist < dist[neighbor]) {
                    dist[neighbor] = new_dist;
                    pq.push({neighbor, new_dist});
                }
            }
        }
    }
}

案例二：任务调度系统

假设需要按优先级处理任务，优先级越高的任务越早执行：

#include <queue>
#include <string>

struct Task {
    int priority;   // 优先级数值（0为最高）
    std::string description;
    bool operator>(const Task& other) const {
        return priority > other.priority; // 小顶堆：优先级0的任务先出队
    }
};

void task_scheduler() {
    std::priority_queue<Task, std::vector<Task>, std::greater<Task>> task_queue;
    
    task_queue.push({0, "Critical system check"}); // 优先级最高
    task_queue.push({2, "User login event"});
    task_queue.push({1, "Background data sync"});
    
    while (!task_queue.empty()) {
        Task current = task_queue.top();
        task_queue.pop();
        std::cout << "Processing: " << current.description << std::endl;
    }
}

高级技巧与常见问题

技巧一：使用自定义数据类型

若需存储复杂对象（如结构体或类），需重载比较运算符或定义仿函数：

struct Person {
    std::string name;
    int age;
    bool operator>(const Person& other) const {
        return age > other.age; // 按年龄从小到大排序
    }
};

int main() {
    std::priority_queue<Person, std::vector<Person>, std::greater<Person>> people;
    people.push({"Alice", 30});
    people.push({"Bob", 25});
    std::cout << "Youngest person: " << people.top().name << std::endl; // 输出 Bob
    return 0;
}

技巧二：避免隐式类型转换陷阱

当使用自定义比较函数时，需确保参数类型与实际存储类型一致。例如，若存储 int，但比较函数接受 double，会导致编译错误。

性能优化建议

  1. 减少不必要的 top() 调用：频繁访问堆顶可能影响性能，建议合并操作。
  2. 选择合适的底层容器：默认使用 std::vector，若需其他底层容器（如 deque），需在模板参数中指定。

总结

<priority_queue> 是 C++ 中一个高效且灵活的容器类，其通过堆结构实现了快速的优先级访问。无论是处理算法优化还是实际系统开发，掌握其核心原理与使用技巧都能显著提升代码效率。通过本文的代码示例与案例分析，读者可以逐步理解如何根据需求选择最大堆或最小堆，并灵活应用到项目中。

在后续学习中，建议进一步探索堆的底层实现细节，或尝试用 <priority_queue> 解决更复杂的场景（如事件调度、资源分配等）。掌握这一工具，将为开发高性能的 C++ 程序奠定坚实的基础。

最新发布

查看更多文章