🔬 c++标准库里优先队列是怎么实现的？

📋 总结

📖 内容概览 本文将详细介绍C++标准库中priority_queue（优先队列）的底层实现原理，包括堆的概念、建堆算法、堆操作，以及优先队列的各种使用方式。通过深入理解优先队列的实现机制，帮助开发者在实际项目中正确高效地使用这一数据结构。 📚 优先队列的基本概念

1.1 什么是优先队列

优先队列（Priority Queue）是一种特殊的队列，它的特点是：

元素按照优先级进行排序
每次取出的元素都是当前队列中优先级最高的元素
插入元素时会自动调整位置，保持优先级顺序在C++ STL中，priority_queue默认是最大堆（Max Heap），即每次取出的是最大元素。

1.2 优先队列的应用场景

优先队列常用于以下场景：

任务调度系统（按优先级处理任务）
图算法（如Dijkstra最短路径、Prim最小生成树）
排序算法（堆排序）
数据流中的中位数查找
霍夫曼编码 🎯 优先队列的底层实现

2.1 堆的概念

C++ STL中的优先队列基于堆（Heap）数据结构实现。堆是一种特殊的完全二叉树，具有以下性质：

最大堆：每个节点的值都大于或等于其子节点的值
最小堆：每个节点的值都小于或等于其子节点的值堆通常用数组（vector）来表示，利用完全二叉树的性质进行索引：
对于索引为i的节点：
- 左子节点索引：2i + 1
- 右子节点索引：2i + 2
- 父节点索引：(i - 1) / 2

2.2 优先队列的定义

在C++ STL中，priority_queue的定义如下：

1
template <
2
    class T,
3
    class Container = std::vector<T>,
4
    class Compare = std::less<typename Container::value_type>
5
> class priority_queue;

T：存储的元素类型
Container：底层容器类型，默认为std::vector<T>
Compare：比较函数对象，默认为std::less<>（最大堆） 🔧 堆的核心操作

3.1 下滤操作（Sift Down）

下滤操作用于维护堆的性质，当根节点被替换后，需要将新的根节点向下调整到合适位置。

1
void sift_down(vector<int>& heap, int start, int end) {
2
    int parent = start;
3
    int child = 2 * parent + 1; // 左子节点
4

5
    while (child <= end) {
6
        // 选择左右子节点中较大的那个
7
        if (child + 1 <= end && heap[child] < heap[child + 1]) {
8
            child++;
9
        }
10

11
        // 如果父节点大于等于子节点，堆性质已满足
12
        if (heap[parent] >= heap[child]) {
13
            return;
14
        } else {
15
            // 交换父节点和子节点
16
            swap(heap[parent], heap[child]);
17
            // 继续向下调整
18
            parent = child;
19
            child = 2 * parent + 1;
20
        }
21
    }
22
}

3.2 上滤操作（Sift Up）

上滤操作用于在插入新元素时，将新元素向上调整到合适位置，以维护堆的性质。

1
void sift_up(vector<int>& heap, int start) {
2
    int child = start;
3
    int parent = (child - 1) / 2; // 父节点
4

5
    while (child > 0 && heap[child] > heap[parent]) {
6
        // 交换子节点和父节点
7
        swap(heap[child], heap[parent]);
8
        // 继续向上调整
9
        child = parent;
10
        parent = (child - 1) / 2;
11
    }
12
}

3.3 建堆算法

建堆算法使用Floyd算法，从最后一个非叶子节点开始，自下而上进行下滤操作。

1
void build_heap(vector<int>& heap) {
2
    int n = heap.size();
3
    // 从最后一个非叶子节点开始，向前遍历
4
    for (int i = n / 2 - 1; i >= 0; --i) {
5
        sift_down(heap, i, n - 1);
6
    }
7
}

建堆的时间复杂度为O(n)，优于逐个插入元素的O(n log n)。 💡 优先队列的基本操作

4.1 优先队列的创建

1
#include <queue>
2
#include <vector>
3
#include <functional>
4

5
// 1. 默认最大堆
6
std::priority_queue<int> max_heap;
7

8
// 2. 显式指定最大堆
9
std::priority_queue<int, std::vector<int>, std::less<int>> max_heap2;
10

11
// 3. 最小堆
12
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

4.2 常用成员函数

成员函数	功能	时间复杂度
`push(const T& value)`	插入元素	O(log n)
`pop()`	删除堆顶元素	O(log n)
`top()`	返回堆顶元素	O(1)
`empty()`	检查是否为空	O(1)
`size()`	返回元素个数	O(1)

4.3 优先队列的使用示例

1
#include <iostream>
2
#include <queue>
3

4
int main() {
5
    // 创建最大堆
6
    std::priority_queue<int> pq;
7

8
    // 插入元素
9
    pq.push(3);
10
    pq.push(1);
11
    pq.push(4);
12
    pq.push(5);
13

14
    // 输出堆顶元素
15
    std::cout << "堆顶元素: " << pq.top() << std::endl; // 输出: 5
16

17
    // 弹出堆顶元素
18
    pq.pop();
19
    std::cout << "弹出后堆顶元素: " << pq.top() << std::endl; // 输出: 4
20

21
    // 遍历所有元素（会破坏堆结构）
22
    std::cout << "所有元素: ";
23
    while (!pq.empty()) {
24
        std::cout << pq.top() << " ";
25
        pq.pop();
26
    }
27
    // 输出: 4 3 1
28

29
    return 0;
30
}

🚀 优先队列的高级使用

5.1 存储pair类型

优先队列可以存储pair类型，默认按照pair的第一个元素进行比较，第一个元素相同时比较第二个元素。

1
#include <iostream>
2
#include <queue>
3
#include <utility>
4
#include <string>
5

6
int main() {
7
    // 最大堆（默认）
8
    std::priority_queue<std::pair<int, std::string>> pq;
9

10
    pq.push({3, "apple"});
11
    pq.push({1, "banana"});
12
    pq.push({4, "cherry"});
13
    pq.push({1, "date"});
14

15
    // 遍历所有元素
16
    while (!pq.empty()) {
17
        auto [priority, name] = pq.top();
18
        std::cout << "优先级: " << priority << ", 名称: " << name << std::endl;
19
        pq.pop();
20
    }
21

22
    return 0;
23
}

输出结果：

1
优先级: 4, 名称: cherry
2
优先级: 3, 名称: apple
3
优先级: 1, 名称: date
4
优先级: 1, 名称: banana

5.2 自定义比较函数

5.2.1 重载operator<

对于自定义类型，可以通过重载operator<来定义比较规则：

1
#include <iostream>
2
#include <queue>
3
#include <string>
4

5
struct Task {
6
    int priority;
7
    std::string name;
8

9
    // 重载operator<，定义最大堆
10
    bool operator<(const Task& other) const {
11
        return priority < other.priority;
12
    }
13
    // 若要定义最小堆，返回 priority > other.priority
14
};
15

16
int main() {
17
    std::priority_queue<Task> pq;
18
    pq.push({3, "Task A"});
19
    pq.push({1, "Task B"});
20
    pq.push({5, "Task C"});
21

22
    std::cout << "任务: " << pq.top().name << ", 优先级: " << pq.top().priority << std::endl;
23
    // 输出: 任务: Task C, 优先级: 5
24

25
    return 0;
26
}

5.2.2 使用函数对象

1
#include <iostream>
2
#include <queue>
3
#include <string>
4

5
struct Task {
6
    int priority;
7
    std::string name;
8
};
9

10
// 自定义比较函数对象（最小堆）
11
struct CompareTask {
12
    bool operator()(const Task& t1, const Task& t2) {
13
        return t1.priority > t2.priority;
14
    }
15
};
16

17
int main() {
18
    std::priority_queue<Task, std::vector<Task>, CompareTask> pq;
19
    pq.push({3, "Task A"});
20
    pq.push({1, "Task B"});
21
    pq.push({5, "Task C"});
22

23
    std::cout << "任务: " << pq.top().name << ", 优先级: " << pq.top().priority << std::endl;
24
    // 输出: 任务: Task B, 优先级: 1
25

26
    return 0;
27
}

5.2.3 使用lambda表达式

C++11及以上支持使用lambda表达式作为比较函数：

1
#include <iostream>
2
#include <queue>
3

4
int main() {
5
    // 定义lambda比较函数（最小堆）
6
    auto cmp = [](int a, int b) {
7
        return a > b;
8
    };
9

10
    // 使用decltype获取lambda的类型
11
    std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);
12

13
    pq.push(3);
14
    pq.push(1);
15
    pq.push(4);
16

17
    // 输出所有元素
18
    std::cout << "所有元素: ";
19
    while (!pq.empty()) {
20
        std::cout << pq.top() << " ";
21
        pq.pop();
22
    }
23
    // 输出: 1 3 4
24

25
    return 0;
26
}

🔍 优先队列的实现原理深度解析

6.1 push操作的实现

当调用push()插入元素时，优先队列的实现逻辑如下：

将新元素添加到底层容器的末尾
对新元素执行上滤操作，使其上升到合适位置

1
void push(const value_type& val) {
2
    // 1. 添加到末尾
3
    c.push_back(val);
4
    // 2. 上滤操作
5
    sift_up(c.size() - 1, val);
6
}

6.2 pop操作的实现

当调用pop()删除堆顶元素时，优先队列的实现逻辑如下：

将堆顶元素与底层容器的最后一个元素交换
删除最后一个元素（原堆顶元素）
对新的堆顶元素执行下滤操作，使其下降到合适位置

1
void pop() {
2
    // 1. 检查是否为空
3
    if (c.empty()) return;
4
    // 2. 交换堆顶和最后一个元素
5
    std::swap(c.front(), c.back());
6
    // 3. 删除最后一个元素
7
    c.pop_back();
8
    // 4. 下滤操作
9
    if (!c.empty()) {
10
        sift_down(0, c.front());
11
    }
12
}

6.3 top操作的实现

top()操作非常简单，直接返回底层容器的第一个元素：

1
const_reference top() const {
2
    return c.front();
3
}

⏱️ 优先队列的性能分析

7.1 时间复杂度

操作	时间复杂度	说明
插入（push）	O(log n)	需要上滤操作
删除（pop）	O(log n)	需要下滤操作
访问堆顶（top）	O(1)	直接返回第一个元素
建堆	O(n)	Floyd算法

7.2 空间复杂度

优先队列的空间复杂度为O(n)，其中n是元素个数，主要用于存储底层容器。

7.3 与其他容器的比较

容器	插入复杂度	删除复杂度	访问最大/最小元素	顺序
`priority_queue`	O(log n)	O(log n)	O(1)	无序（仅堆顶有序）
`set`	O(log n)	O(log n)	O(log n)	有序
`unordered_set`	O(1) 平均	O(1) 平均	O(n)	无序
`vector`	O(1) 尾部	O(n)	O(n)	有序/无序
🌟 优先队列的最佳实践

8.1 选择合适的比较方式

默认情况下，优先队列是最大堆
使用std::greater<>可以创建最小堆
对于自定义类型，根据需要重载operator<或提供比较函数

8.2 避免频繁的push和pop操作

频繁的push和pop操作会导致多次堆调整，影响性能
如果需要批量处理元素，考虑先构建堆，再进行操作

8.3 注意内存使用

优先队列的底层容器默认是vector，会动态扩容
对于大量元素，可以使用reserve()预先分配空间

8.4 自定义类型的注意事项

确保比较函数是严格弱序（Strict Weak Ordering）
比较函数应该是const成员函数或函数对象
避免在比较函数中修改对象状态 📋 总结

9.1 优先队列的核心要点

底层实现：基于堆数据结构，默认为最大堆
存储结构：使用vector作为底层容器，利用完全二叉树的性质
核心操作：上滤（插入）和下滤（删除）
时间复杂度：插入和删除均为O(log n)，访问堆顶为O(1)
灵活性：支持自定义比较函数，可以实现最大堆或最小堆

9.2 优先队列的使用建议

当需要频繁访问最大/最小元素时，优先使用优先队列
当需要有序遍历所有元素时，考虑使用set或sort后的vector
当元素数量较大时，注意内存使用和预先分配空间
对于自定义类型，确保比较函数正确实现

9.3 优先队列与堆排序的关系

优先队列的实现原理与堆排序密切相关：

堆排序的第一步是建堆，与优先队列的初始化类似
堆排序的第二步是反复取出堆顶元素，与优先队列的pop操作类似
优先队列可以看作是堆排序的动态版本，支持动态插入和删除元素通过深入理解优先队列的实现原理和使用方法，可以在实际项目中正确选择和高效使用这一重要的数据结构，提高程序的性能和可读性。

Gxy' Blog

48.c++标准库里优先队列是怎么实现的？

🔬 c++标准库里优先队列是怎么实现的？

📋 总结

1.1 什么是优先队列

1.2 优先队列的应用场景

2.1 堆的概念

2.2 优先队列的定义

3.1 下滤操作（Sift Down）

3.2 上滤操作（Sift Up）

3.3 建堆算法

4.1 优先队列的创建

4.2 常用成员函数

4.3 优先队列的使用示例

5.1 存储pair类型

5.2 自定义比较函数

5.2.1 重载operator<

5.2.2 使用函数对象

5.2.3 使用lambda表达式

6.1 push操作的实现

6.2 pop操作的实现

6.3 top操作的实现

7.1 时间复杂度

7.2 空间复杂度

7.3 与其他容器的比较

8.1 选择合适的比较方式

8.2 避免频繁的push和pop操作

8.3 注意内存使用

8.4 自定义类型的注意事项

9.1 优先队列的核心要点

9.2 优先队列的使用建议

9.3 优先队列与堆排序的关系

48.c++标准库里优先队列是怎么实现的？

评论区

目录

Gxy' Blog

4.面向对象的特性：多态原理

22.C++新特性概览

23.类型转换

45.new可以重载吗，可以改写new函数吗

54.C++的单元测试

48.c++标准库里优先队列是怎么实现的？

🔬 c++标准库里优先队列是怎么实现的？

📋 总结

1.1 什么是优先队列

1.2 优先队列的应用场景

2.1 堆的概念

2.2 优先队列的定义

3.1 下滤操作（Sift Down）

3.2 上滤操作（Sift Up）

3.3 建堆算法

4.1 优先队列的创建

4.2 常用成员函数

4.3 优先队列的使用示例

5.1 存储pair类型

5.2 自定义比较函数

5.2.1 重载operator<

5.2.2 使用函数对象

5.2.3 使用lambda表达式

6.1 push操作的实现

6.2 pop操作的实现

6.3 top操作的实现

7.1 时间复杂度

7.2 空间复杂度

7.3 与其他容器的比较

8.1 选择合适的比较方式

8.2 避免频繁的push和pop操作

8.3 注意内存使用

8.4 自定义类型的注意事项

9.1 优先队列的核心要点

9.2 优先队列的使用建议

9.3 优先队列与堆排序的关系

48.c++标准库里优先队列是怎么实现的？

评论区

目录