priority_queue实现大顶堆

priority_queue默认是小顶堆，如果要实现大顶堆，可以通过两种方式：

1. 自定义比较函数

可以自定义比较函数，使得priority_queue按照我们定义的方式进行排序。比如，如果我们要实现大顶堆，可以定义一个比较函数，使得较大的元素排在前面。

struct cmp {
    bool operator() (int a, int b) {
        return a < b; // 小于号改为大于号
    }
};
priority_queue<int, vector<int>, cmp> q; // 第三个参数传入比较函数

2. 借助std::greater

可以将priority_queue的第三个参数设置为std::greater，这样就可以实现大顶堆。

priority_queue<int, vector<int>, greater<int>> q; // 第三个参数传入std::greater

两种方式都可以实现大顶堆，根据需要选择即可。

相关问题

priority_queue c++ 大顶堆

在C++中，`priority_queue` 是一种容器适配器，默认情况下实现的是一个最大堆（max heap），即优先级最高的元素总是位于堆顶。`priority_queue` 通常基于 `vector` 实现，并使用一个堆算法来处理元素。

### 主要特点
1. **默认大顶堆**：默认情况下，`priority_queue` 是一个大顶堆，堆顶元素是最大的。
2. **不支持随机访问**：只能访问堆顶元素，无法直接访问其他元素。
3. **基本操作**：主要操作包括 `push`（插入元素）、`pop`（删除堆顶元素）和 `top`（访问堆顶元素）。

### 基本用法

#include <iostream>
#include <queue>

int main() {
    // 创建一个大顶堆
    std::priority_queue<int> pq;

    // 插入元素
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // 访问堆顶元素
    std::cout << "Top element: " << pq.top() << std::endl; // 输出 30

    // 删除堆顶元素
    pq.pop();

    // 再次访问堆顶元素
    std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 20

    return 0;
}

### 自定义比较器
如果需要实现一个小顶堆，可以使用自定义比较器。例如，使用 `std::greater` 作为比较器：

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

int main() {
    // 创建一个小顶堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    // 插入元素
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // 访问堆顶元素
    std::cout << "Top element: " << pq.top() << std::endl; // 输出 10

    // 删除堆顶元素
    pq.pop();

    // 再次访问堆顶元素
    std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 20

    return 0;
}

### 常见操作
- `push(x)`: 插入元素 `x`
- `pop()`: 删除堆顶元素
- `top()`: 访问堆顶元素
- `empty()`: 检查堆是否为空
- `size()`: 返回堆中元素的数量

通过这些操作，可以方便地使用 `priority_queue` 来实现各种优先队列的功能。

priority_queue小顶堆

小顶堆是一种优先级队列的实现方式，其中元素的优先级由小到大排列。在C++中，可以使用priority_queue容器来实现小顶堆。例如，可以使用以下代码定义一个小顶堆的priority_queue：

priority_queue<int, vector<int>, greater<int>> pq;

在这个定义中，第一个参数int表示元素的类型，第二个参数vector<int>表示底层容器的类型，第三个参数greater<int>表示比较函数，用于确定元素的优先级。通过使用greater<int>，可以确保小的元素在堆顶。可以使用pq.top()来获取小顶堆中优先级最高的元素，使用pq.pop()来弹出优先级最高的元素。
#### 引用[.reference_title]
- *1* *2* [优先级队列: 搞懂大顶堆和小顶堆 c++](https://blog.csdn.net/qq_40286920/article/details/126027995)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insertT0,239^v3^insert_chatgpt"}} ] [.reference_item]
- *3* [C++堆/优先队列-STL-priority_queue](https://blog.csdn.net/YBYB_mark/article/details/125582061)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^insertT0,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]