2.8、说一说你了解的优先级队列？

关键特性与实现原理

底层容器

• • 默认使用 std::vector 作为底层存储容器
• • 也可指定为 std::deque 等支持随机访问迭代器的容器
• • 要求底层容器支持 push_back 和 pop_back 操作，以便维护堆结构

堆结构维护

• • 利用堆算法（make_heap、push_heap、pop_heap）维护元素顺序
• • 默认为最大堆（优先级最高元素最大，位于堆顶）

访问与操作接口

优先级定义

• • 默认比较函数：std::less<T>（实现最大堆，较大元素优先）
• • 自定义方式：
  • • 第三个模板参数传入 std::greater<T> 实现最小堆
  • • 自定义仿函数或重载 operator< 实现复杂优先级规则

使用示例

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

int main() {
    // 最大堆（默认）
    std::priority_queue<int> maxHeap;
    maxHeap.push(10);
    maxHeap.push(30);
    maxHeap.push(20);
    std::cout << maxHeap.top() << std::endl; // 输出30

    // 最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(10);
    minHeap.push(30);
    minHeap.push(20);
    std::cout << minHeap.top() << std::endl; // 输出10

    return 0;
}

性能优势

• • 插入/删除操作：O(log N)
• • 访问最大元素：O(1)
• • 适用场景：频繁动态维护优先级的场景（如任务调度、Dijkstra算法优化等）
  本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
  （加入我的知识星球，免费获取账号，解锁所有文章。）