当前位置：首页 > article >正文

STL容器之priority_queue的常用功能和操作

article 2024/11/23 16:14:50

在C++标准模板库（STL）中，priority_queue是一个非常重要的容器适配器，它提供了一个优先级队列的功能，允许元素根据优先级进行排序。这种数据结构在许多算法和应用中都非常有用，比如任务调度、Dijkstra算法中的边权最短路径问题等。

基本功能

定义与特性

主要操作

默认行为

应用场景

实例

代码解析

基本功能

定义与特性

priority_queue是一个出队时总是取出最大元素的队列，它默认使用元素类型的<操作符来确定元素的优先级，即默认为大顶堆。priority_queue只允许对队列的顶部元素进行访问，即最大的元素。

主要操作

empty()：检查队列是否为空。
size()：返回队列中的元素数量。
top()：访问队列顶部的元素（不删除）。
push()：向队列中添加一个元素。
pop()：移除队列顶部的元素。

默认行为

默认情况下，priority_queue是一个最大值优先的队列。如果你需要一个最小值优先的队列，可以通过传递第三个模板参数greater<ValueType>来实现。当处理的数据不仅仅是简单的数值，而是包含多个属性的结构体时，priority_queue可以通过自定义比较函数来处理这些结构化数据。

应用场景

priority_queue在需要根据优先级处理元素的场景中非常有用，例如：

任务调度：根据任务的紧急程度来处理。
Dijkstra算法：用于存储未访问顶点的边权值。
Huffman编码：用于构建最优前缀编码。

实例

#include <bits/stdc++.h>
using namespace std;

struct game {
    int year;
    int money;
};

struct compare_outbig {
    bool operator()(const game& game1, const game& game2) {
        return game1.money < game2.money; // 钱少的在堆下，多的在顶部，输出最大的
    }
};

struct compare_outsmall {
    bool operator()(const game& game1, const game& game2) {
        return game1.money > game2.money; // 钱多的在堆下，少的在顶部，输出最小的
    }
};

int main() {
    priority_queue<int> out_big;
    priority_queue<int, vector<int>, greater<int>> out_small;
    priority_queue<game, vector<game>, compare_outbig> struct_out_big;
    priority_queue<game, vector<game>, compare_outsmall> struct_out_small;

    int n = 1;
    while (n) {
        cin >> n;
        out_big.push(n);
        out_small.push(n);
    }

    int m = 1;
    while (m) {
        cin >> n >> m;
        game sample1;
        sample1.year = n;
        sample1.money = m;
        struct_out_big.push(sample1);
        struct_out_small.push(sample1);
    }

    cout << "out_big" << endl;
    while (!out_big.empty()) {
        cout << out_big.top() << endl;
        out_big.pop();
    }

    cout << "out_small" << endl;
    while (!out_small.empty()) {
        cout << out_small.top() << endl;
        out_small.pop();
    }

    cout << "struct_out_big" << endl;
    while (!struct_out_big.empty()) {
        game sample1 = struct_out_big.top();
        cout << "game_money:" << sample1.money << "game_:" << sample1.year << endl;
        struct_out_big.pop();
    }

    cout << "struct_out_small" << endl;
    while (!struct_out_small.empty()) {
        game sample1 = struct_out_small.top();
        cout << "game_money:" << sample1.money << "game_:" << sample1.year << endl;
        struct_out_small.pop();
    }

    return 0;
}