priority_queue begin

### 一、queue 和 priority_queue 的定义 `queue` 是一种 FIFO（First In First Out，先进先出）的线性数据结构[^4]。这意味着最早进入队列的元素会最先被移除。 而 `priority_queue` 则是一种基于堆的数据结构，其核心特点是：无论何时插入新元素，队列头部总是具有最高优先级的元素[^1]。默认情况下，`priority_queue` 使用最大堆来实现，因此顶部元素是当前队列中最大的值。 --- ### 二、queue 和 priority_queue 的主要区别 #### 1. 数据存取逻辑 - **Queue**: 遵循严格的 FIFO 原则，即最先进入队列的元素会被最先取出。 - **Priority Queue**: 不遵循 FIFO 原则，而是依据元素的优先级决定哪个元素应被最先取出。通常来说，优先级最高的元素会在队首位置[^4]。 #### 2. 底层实现机制 - **Queue**: 默认使用双端队列 (`deque`) 实现，支持两端操作 (front 和 back)[^4]。 - **Priority Queue**: 默认使用向量 (`vector`) 结合堆算法实现，底层是一个完全二叉树表示的最大堆或最小堆[^3]。 #### 3. 插入与删除效率 - 对于普通的 `queue`，插入和删除的时间复杂度均为 O(1)，因为只需要调整队尾或队头指针即可完成相应操作。 - 而对于 `priority_queue`，由于每次都需要维护堆性质，插入时间为 O(log n)，弹出同样为 O(log n) 时间复杂度[^5]。 #### 4. 自定义比较函数的支持程度 - **Queue**: 不允许自定义排序规则，仅能按固定顺序依次进出。 - **Priority Queue**: 支持通过模板参数传递自定义比较器（如 `std::greater<T>` 或其他用户定义的谓词类），从而灵活改变优先级判断标准[^5]。 --- ### 三、queue 和 priority_queue 的典型应用场景 #### 1. Queue 的适用场景 当需要严格按照时间序列处理任务或者消息时可以考虑使用普通队列。例如： - CPU调度中的轮转法(Round Robin Scheduling) - 广度优先搜索(BFS) ```cpp #include <iostream> #include <queue> using namespace std; void demoQueue() { queue<int> q; q.push(1); q.push(2); cout << "Front item: " << q.front() << endl; // 输出 Front item: 1 q.pop(); cout << "After pop, front item: " << q.front() << endl; // After pop, front item: 2 } ``` #### 2. Priority Queue 的适用场景 如果希望根据某些特定条件动态安排待办事项，则更适合选用带权重管理功能的优先权队列。比如： - Dijkstra算法求解单源最短路径问题； - Huffman编码构建最优前缀码表过程等等。 下面展示了一个简单的例子演示如何利用 C++ STL 提供的功能创建一个小顶堆： ```cpp #include <functional> #include <queue> #include <vector> #include <iostream> using namespace std; void demoPriorityQueue(){ vector<int> nums = {2, 9, 1, 6, 7, 4 ,0}; priority_queue<int,vector<int>,greater<int>> minHeap(nums.begin(),nums.end()); while(!minHeap.empty()){ cout<<minHeap.top()<<" "; minHeap.pop(); } } // Output will be : 0 1 2 4 6 7 9 ``` --- ### 四、总结对比表格 | 特性 | Queue | Priority Queue | |---------------------|----------------------------------|------------------------------------| | 存储模型 | FIFO | 根据优先级 | | 底层实现 | deque | vector | | 插入/删除复杂度 | O(1)/O(1) | O(log N)/O(log N) | | 是否可定制排序 | 否 | 可 | ---

priority_queue是一个STL容器，它是一个优先级队列，可以用来实现堆。在使用priority_queue之前，需要对其进行初始化。priority_queue的初始化有两种方式：一种是使用默认的构造函数，另一种是使用已有数组对其进行初始化。 使用默认的构造函数初始化priority_queue的语法如下： priority_queue<type, container, function> pq; 其中，type是存储在队列中的元素类型，container是底层容器类型，默认为vector，function是元素比较函数，默认为less<type>，即大顶堆。 使用已有数组对priority_queue进行初始化的语法如下： priority_queue<type, container, function> pq(input.begin(), input.end()); 其中，input是已有数组，begin()和end()是数组的起始和结束迭代器。 需要注意的是，如果要使用小顶堆，需要将function参数设置为greater<type>。