C++优先队列用法知识点总结

优先队列简介

优先队列是一个具有优先级的队列，可以确保元素按照一定的优先级顺序出队。C++中的优先队列底层使用堆实现，因此其时间复杂度为O(logn)。

优先队列的基本操作

插入一个元素

C++中，插入一个元素可以使用push()函数。

#include <queue>

priority_queue<int> my_pq; // 定义一个默认降序排列的优先队列
my_pq.push(10); // 向优先队列插入元素10

弹出队首元素

优先队列弹出队首元素可以使用pop()函数。

#include <queue>

priority_queue<int> my_pq;
my_pq.push(10);
my_pq.push(20);
my_pq.pop(); // 弹出队首元素10

获取队首元素

优先队列获取队首元素可以使用top()函数。

#include <queue>

priority_queue<int> my_pq;
my_pq.push(10);
my_pq.push(20);
int front_elem = my_pq.top(); // 获取队首元素20

优先队列的排序方式

默认降序

默认情况下，C++中的优先队列是按照元素的大小进行降序排列的。

#include <queue>

priority_queue<int> my_pq;
my_pq.push(10);
my_pq.push(20);
my_pq.push(5);
// 输出20 10 5
while (!my_pq.empty()) {
    cout << my_pq.top() << " ";
    my_pq.pop();
}

升序排列

我们可以通过定义自定义结构体或使用函数对象改变默认的降序排列，从而实现升序排列。

#include <queue>

struct cmp {
    bool operator() (int a, int b) {
        return a > b;
    }
};

priority_queue<int, vector<int>, cmp> my_pq;
my_pq.push(10);
my_pq.push(20);
my_pq.push(5);
// 输出5 10 20
while (!my_pq.empty()) {
    cout << my_pq.top() << " ";
    my_pq.pop();
}

复杂对象的排序

对于复杂对象，我们需要定义一个比较函数来完成排序。

#include <queue>
#include <string>

struct person {
    string name;
    int age;
};

struct cmp {
    bool operator() (const person& a, const person& b) {
        return a.age > b.age; // 按照年龄从小到大排列
    }
};

priority_queue<person, vector<person>, cmp> my_pq;
my_pq.push({"Mike", 25});
my_pq.push({"Tom", 18});
my_pq.push({"Jerry", 29});
// 按照年龄顺序输出Tom, Mike, Jerry
while (!my_pq.empty()) {
    cout << my_pq.top().name << " ";
    my_pq.pop();
}

示例说明

示例1

题目描述：从一个大小为n的整数数组中选择k个数，使它们的和最大。

首先，我们可以把这个数组放入一个降序排序的优先队列中。按照优先队列的定义，队首元素是最大的，这样我们可以从队列中弹出前k个元素，它们的和就是我们要的最大和。

#include <queue>
#include <vector>

using namespace std;

int find_max_sum(vector<int>& nums, int k) {
    priority_queue<int> my_pq(nums.begin(), nums.end());

    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += my_pq.top();
        my_pq.pop();
    }

    return sum;
}

int main() {
    vector<int> nums = {1, 4, 2, 3, 5, 7, 6};
    int k = 3;
    int max_sum = find_max_sum(nums, k); // 返回18
    return 0;
}

示例2

题目描述：在一个无序的序列中，找到第k大的数。

这个问题可以使用降序排列的小根堆来解决。首先，将数组中的前k个数放入小根堆中；然后遍历剩余的数，如果遇到比堆顶元素大的数，就将其弹出，将该数插入堆中。最后，堆顶元素就是第k大的数。

#include <queue>
#include <vector>

using namespace std;

int find_kth_largest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> my_pq(nums.begin(), nums.begin() + k);

    for (int i = k; i < nums.size(); i++) {
        if (nums[i] > my_pq.top()) {
            my_pq.pop();
            my_pq.push(nums[i]);
        }
    }

    return my_pq.top();
}

int main() {
    vector<int> nums = {1, 4, 2, 3, 5, 7, 6};
    int k = 3;
    int kth_largest = find_kth_largest(nums, k); // 返回5
    return 0;
}