Data-Structure/std-Cpp/STL/STL-priority_queue

好的！我来给你详细介绍一下 C++ STL 里的 priority_queue 容器适配器的用法和常见技巧，帮你全面掌握它。

---

一、什么是 priority_queue？

priority_queue 是 STL 提供的一个容器适配器，底层默认使用堆（heap）数据结构实现，保证访问时总能快速取得最大（默认）或最小元素。

它类似于一个“优先级队列”，总是先弹出优先级最高（优先级依据元素大小）的元素。

---

二、包含头文件

#include <queue>

priority_queue 位于 <queue> 头文件中。

---

三、定义和基本用法

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;  // 默认大顶堆，元素类型为int

    pq.push(5);
    pq.push(1);
    pq.push(10);
    pq.push(7);

    // 访问优先级最高的元素（最大值）
    std::cout << "Top: " << pq.top() << "\n"; // 10

    // 弹出元素，优先级最高的先出
    pq.pop();

    std::cout << "Top after pop: " << pq.top() << "\n"; // 7

    return 0;
}

---

四、构造函数（常见形式）

priority_queue();

priority_queue(const Compare& comp);  // 指定比较函数

priority_queue(const Compare& comp, const Container& cont);

priority_queue(const priority_queue& other);

---

五、成员函数

函数	说明
push(const T& val)	插入元素
pop()	删除堆顶元素
top()	返回堆顶元素（最大或最小）
empty()	判断是否为空
size()	返回元素个数
emplace(args...)	原地构造并插入元素
swap(priority_queue&)	交换两个优先队列

---

六、默认是大顶堆，怎么做小顶堆？

默认情况下，priority_queue 采用 std::less<T>，即大顶堆。

方法1：用 std::greater<T>

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

minHeap.push(3);
minHeap.push(10);
minHeap.push(1);

std::cout << minHeap.top() << "\n";  // 1

说明：

• 第二个模板参数是底层容器，默认是 std::vector<T>
• 第三个模板参数是比较器，默认是 std::less<T>（大顶堆）
• 改成 std::greater<T> 就是小顶堆

---

七、自定义比较器

1. 函数对象

struct Compare {
    bool operator()(int a, int b) {
        return a > b; // 这里定义小顶堆
    }
};

std::priority_queue<int, std::vector<int>, Compare> pq;

2. Lambda 表达式（C++11 及以上）

auto cmp = [](int left, int right) { return left > right; };
std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);

pq.push(4);
pq.push(2);
pq.push(8);

std::cout << pq.top() << "\n";  // 2

---

八、优先队列存储自定义类型

假设你有一个结构体：

struct Person {
    std::string name;
    int age;
};

// 按年龄从大到小排序（大顶堆）
struct ComparePerson {
    bool operator()(const Person& a, const Person& b) {
        return a.age < b.age;  // 年龄大的优先级高
    }
};

std::priority_queue<Person, std::vector<Person>, ComparePerson> pq;

使用：

pq.push({"Alice", 30});
pq.push({"Bob", 25});
pq.push({"Cindy", 35});

auto top = pq.top();
std::cout << top.name << " " << top.age << "\n";  // Cindy 35

---

九、注意事项和技巧

• priority_queue 不能遍历和访问除堆顶以外的元素。
• 如果需要修改某个元素的优先级，通常做法是重新插入修改后的元素，旧元素保留或标记过期。
• emplace() 比 push() 直接传入构造参数，效率更高。

---

十、示例综合

#include <iostream>
#include <queue>
#include <vector>
#include <string>

struct Task {
    std::string name;
    int priority;
};

struct TaskCmp {
    bool operator()(const Task& a, const Task& b) {
        return a.priority < b.priority;  // 大顶堆
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, TaskCmp> tasks;

    tasks.emplace(Task{"Task1", 5});
    tasks.push({"Task2", 1});
    tasks.push({"Task3", 10});

    while (!tasks.empty()) {
        Task t = tasks.top();
        std::cout << t.name << ": " << t.priority << "\n";
        tasks.pop();
    }

    return 0;
}

输出：

Task3: 10
Task1: 5
Task2: 1

---

好的！这里给你整理一个C++ STL priority_queue 的全面使用方法大全，包含它的构造函数、所有成员函数（含继承自底层容器的限制），以及使用示例和细节说明。

---

STL priority_queue 完整介绍

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

• T：元素类型
• Container：底层容器类型，必须满足随机访问迭代器，默认是 std::vector<T>
• Compare：排序规则，默认是 std::less<T>（大顶堆）

---

一、构造函数

函数原型	说明
priority_queue()	默认构造一个空优先队列
explicit priority_queue(const Compare& comp);	使用指定比较器构造空优先队列
priority_queue(const Compare& comp, const Container& cont);	指定比较器和底层容器，拷贝构造
priority_queue(const priority_queue& other);	拷贝构造
priority_queue(priority_queue&& other) noexcept;	移动构造（C++11）
priority_queue& operator=(const priority_queue& other);	拷贝赋值
priority_queue& operator=(priority_queue&& other) noexcept;	移动赋值（C++11）

---

二、成员函数

函数原型	说明
bool empty() const;	判断是否为空
size_type size() const;	返回元素个数
const_reference top() const;	返回堆顶元素（优先级最高元素）
void push(const value_type& val);	插入元素
void push(value_type&& val);	插入右值元素（移动语义，C++11）
template<class... Args> void emplace(Args&&... args);	原地构造插入元素（C++11）
void pop();	弹出堆顶元素
void swap(priority_queue& other) noexcept;	交换两个优先队列
~priority_queue();	析构函数

---

三、底层容器访问（protected）

• priority_queue 不提供直接访问底层容器的接口，但它有一个受保护成员：

protected:
    Container c;

• 如果你继承 priority_queue，可以访问它。

---

四、成员变量说明

• priority_queue 内部维护了一个满足堆性质的容器 c，默认是 vector<T>
• 通过调用 std::push_heap 和 std::pop_heap 保持堆的有序结构。

---

五、示例代码

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // std::greater

int main() {
    // 默认大顶堆
    std::priority_queue<int> pq1;
    pq1.push(5);
    pq1.push(2);
    pq1.push(8);
    std::cout << "Max element: " << pq1.top() << "\n"; // 8

    // 小顶堆，使用 greater 作为比较器
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq2;
    pq2.push(5);
    pq2.push(2);
    pq2.push(8);
    std::cout << "Min element: " << pq2.top() << "\n"; // 2

    // emplace 直接构造
    pq1.emplace(10);
    std::cout << "Max element after emplace: " << pq1.top() << "\n"; // 10

    // pop
    pq1.pop();
    std::cout << "Max element after pop: " << pq1.top() << "\n"; // 8

    return 0;
}

---

六、使用自定义类型

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

struct Person {
    std::string name;
    int age;
};

struct ComparePerson {
    bool operator()(const Person& a, const Person& b) {
        return a.age < b.age; // 按年龄降序（大顶堆）
    }
};

int main() {
    std::priority_queue<Person, std::vector<Person>, ComparePerson> pq;

    pq.push({"Alice", 30});
    pq.push({"Bob", 25});
    pq.push({"Cindy", 35});

    while (!pq.empty()) {
        auto p = pq.top();
        std::cout << p.name << " (" << p.age << ")\n";
        pq.pop();
    }
}

---

七、底层容器可以替换

默认是 std::vector<T>，也可以用 std::deque<T>，但必须支持随机访问迭代器。

std::priority_queue<int, std::deque<int>> pq;

---

八、内部实现原理（简述）

• 底层容器是一个随机访问序列，使用 std::push_heap，std::pop_heap 来维护堆性质。
• push()：先插入底层容器尾部，再调用 push_heap。
• pop()：调用 pop_heap 将最大元素交换到尾部，然后移除尾部元素。
• top()：返回底层容器的第一个元素，即堆顶元素。

---

九、完整成员函数接口（C++标准）

// 构造与析构
priority_queue();
explicit priority_queue(const Compare&);
priority_queue(const Compare&, const Container&);
priority_queue(const priority_queue&);
priority_queue(priority_queue&&) noexcept;
~priority_queue();

// 赋值
priority_queue& operator=(const priority_queue&);
priority_queue& operator=(priority_queue&&) noexcept;

// 访问
bool empty() const;
size_type size() const;
const_reference top() const;

// 修改
void push(const value_type&);
void push(value_type&&);
template <class... Args>
void emplace(Args&&...);
void pop();
void swap(priority_queue&) noexcept;

---

十、注意点

• 只能访问堆顶元素，不能遍历优先队列中的所有元素。
• 如果需要修改队列中间元素的优先级，通常要重新插入，不能直接修改。
• emplace 可以避免不必要的复制，提高效率。
• 默认是大顶堆，如果要小顶堆，改比较器为 std::greater 或自定义。

---

如果你需要，我可以帮你写详细代码示例，或者帮你写自定义比较器的示例！