C++，STL容器适配器，priority_queue：优先队列深入解析

---

一、容器概览与核心特性

std::priority_queue是C++标准模板库（STL）提供的容器适配器，实现优先队列数据结构。元素按优先级排序，队首始终为最大（默认）或最小元素。底层通常基于vector实现堆结构。

---

核心特性速览

特性	说明
底层容器	默认vector，可指定deque
时间复杂度	插入O(log n)，取顶O(1)
空间复杂度	O(n)
迭代器支持	❌ 不支持遍历操作
头文件	<queue>
排序方向	默认大顶堆（可通过比较器修改）

---

二、底层实现原理

1. 二叉堆结构

priority_queue通过完全二叉树实现，满足堆性质：

• 父节点值 ≥ 子节点值（大顶堆）

• 数组存储实现：对于索引i的节点：

  • 父节点：(i-1)/2

  • 左子节点：2*i + 1

  • 右子节点：2*i + 2

    // 堆操作关键函数示意void heapify_up(int i) {while (i > 0 && heap[(i-1)/2] < heap[i]) {swap(heap[(i-1)/2], heap[i]);i = (i-1)/2;}}void heapify_down(int i) {int max = i;if (left(i) < size && heap[left(i)] > heap[max]) max = left(i);if (right(i) < size && heap[right(i)] > heap[max])max = right(i);if (max != i) {swap(heap[i], heap[max]);heapify_down(max);}}

---

2. 容器适配器架构

类声明原型：

    template<typename T,typename Container = vector<T>,typename Compare = less<typename Container::value_type>> class priority_queue;

支持容器需满足：

• front()
• push_back()
• pop_back()
• 随机访问迭代器

---

三、核心操作详解

1. 容器初始化

    // 默认大顶堆priority_queue<int> maxHeap;// 小顶堆初始化priority_queue<int, vector<int>, greater<int>> minHeap;// 自定义比较器struct Task {int priority;string description;};auto cmp = [](const Task& a, const Task& b) {return a.priority < b.priority; // 大顶堆};priority_queue<Task, vector<Task>, decltype