C / C++ / 系统课时

怎样构造一个最小优先队列

怎样构造一个最小优先队列

std::priority_queue 默认把最大元素放在队首。如果业务需要每次优先取最小值,可以使用 std::greater 改变排序方向;元素是自定义类型时,则通过比较器明确“谁的优先级更高”。

学习目标

  • 使用 std::greater 构造最小优先队列
  • 为自定义类型编写符合要求的比较器
  • 理解比较器方向与 top() 返回元素之间的关系

默认行为为什么是最大值优先

std::priority_queue<T> 默认使用 std::less<T> 比较元素,因此 top() 返回当前优先级最高的元素;对于普通数字,这通常就是最大值。

如果希望最小值优先,需要同时指定元素类型、底层容器和比较器:

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

这里的 std::vector<int> 是底层存储容器,std::greater<int> 改变了优先关系,使最小元素出现在 top()。

使用 greater 构造最小优先队列

下面的程序依次压入四个整数,再不断读取和删除队首元素。

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

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minQueue;

    minQueue.push(8);
    minQueue.push(3);
    minQueue.push(10);
    minQueue.push(1);

    while (!minQueue.empty()) {
        std::cout << minQueue.top() << ' ';
        minQueue.pop();
    }

    std::cout << '\n';
    return 0;
}

预期输出

text
1 3 8 10

push() 并不是把数据整体排成一个有序数组,而是维护堆结构。因此应通过 top() 获取当前最小值,通过 pop() 删除它,而不要假设底层元素已经按升序连续排列。

自定义类型需要自定义比较器

当元素没有直接符合业务含义的大小关系时,可以定义比较器。例如任务调度中规定数字越小优先级越高,并在优先级相同时让编号较小的任务先执行。

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

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

struct TaskCompare {
    bool operator()(const Task& a, const Task& b) const {
        // 返回 true 表示 a 的优先级应排在 b 后面。
        if (a.priority != b.priority) {
            return a.priority > b.priority;
        }
        return a.id > b.id;
    }
};

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

    tasks.push({2, 10, "backup"});
    tasks.push({1, 20, "alert"});
    tasks.push({1, 5, "health-check"});

    while (!tasks.empty()) {
        const Task& task = tasks.top();
        std::cout << task.priority << ' ' << task.id << ' ' << task.name << '\n';
        tasks.pop();
    }

    return 0;
}

预期输出

text
1 5 health-check
1 20 alert
2 10 backup

比较器最容易写反的地方

priority_queue 的比较器不能简单理解成“返回 true 的元素排在前面”。更实用的判断方式是:比较器返回 true,表示左侧元素的优先级低于右侧元素。

因此,想让较小的 priority 先出队时,比较器应写成 a.priority > b.priority。如果误写成 <,效果会变成数值较大的任务优先。

对于普通数字,优先使用 std::greater<T>,代码最简洁;只有排序规则包含多个字段或业务语义时,再编写自定义比较器。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

怎样构造一个最小优先队列

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通