快捷導(dǎo)航

C++中std::priority_queue的使用小結(jié)

更新時(shí)間：2025年04月07日 08:37:03 作者：點(diǎn)云SLAM

std::priority_queue是C++ STL提供的優(yōu)先隊(duì)列,本文主要介紹了C++中std::priority_queue的使用小結(jié),具有一定的參考價(jià)值,感興趣的可以了解一下

1. 基本用法

(1) 頭文件

要使用 std::priority_queue，需要包含：

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

(2) 默認(rèn)情況（最大堆）

默認(rèn)情況下，std::priority_queue 是最大堆，即堆頂是最大元素：

std::priority_queue<int> pq;  // 默認(rèn)是最大堆

示例：

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(30);
    pq.push(20);

    std::cout << "堆頂元素：" << pq.top() << std::endl;  // 輸出 30

    pq.pop();  // 移除 30
    std::cout << "新的堆頂：" << pq.top() << std::endl;  // 輸出 20

    return 0;
}

? 特點(diǎn)

push() 插入元素，自動(dòng)維護(hù)最大堆。
top() 獲取當(dāng)前最大元素（堆頂）。
pop() 移除堆頂元素（但不返回它）。
size() 獲取隊(duì)列大小。
empty() 檢查隊(duì)列是否為空。

2. 自定義最小堆

如果要實(shí)現(xiàn) 最小堆（堆頂是最小元素），可以用 std::greater<T>：

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

示例：

#include <iostream>
#include <queue>

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

    pq_min.push(10);
    pq_min.push(30);
    pq_min.push(20);

    std::cout << "堆頂元素：" << pq_min.top() << std::endl;  // 輸出 10

    pq_min.pop();
    std::cout << "新的堆頂：" << pq_min.top() << std::endl;  // 輸出 20

    return 0;
}

? 重點(diǎn)

std::greater<int> 使 priority_queue 變成最小堆。

3. 自定義比較函數(shù)（結(jié)構(gòu)體/仿函數(shù)）

(1) 結(jié)構(gòu)體仿函數(shù)

struct Compare {
    bool operator()(int a, int b) {
        return a > b;  // 最小堆（a > b 表示 a 在 b 下面）
    }
};
std::priority_queue<int, std::vector<int>, Compare> pq;

示例：

#include <iostream>
#include <queue>

struct Compare {
    bool operator()(int a, int b) {
        return a > b;  // 讓小的元素優(yōu)先級高
    }
};

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

    pq.push(10);
    pq.push(30);
    pq.push(20);

    std::cout << "堆頂元素：" << pq.top() << std::endl;  // 輸出 10

    pq.pop();
    std::cout << "新的堆頂：" << pq.top() << std::endl;  // 輸出 20

    return 0;
}

? 優(yōu)點(diǎn)

適用于復(fù)雜的數(shù)據(jù)結(jié)構(gòu)（如 struct）。
允許靈活定義優(yōu)先級。

4. 處理結(jié)構(gòu)體類型

如果 priority_queue 存儲(chǔ)的是自定義結(jié)構(gòu)體，需要提供比較規(guī)則。

(1) 按權(quán)重排序的任務(wù)調(diào)度

#include <iostream>
#include <queue>

struct Task {
    int id;
    int priority;

    // 重載運(yùn)算符，用于最大堆（優(yōu)先級大的優(yōu)先）
    bool operator<(const Task& other) const {
        return priority < other.priority;  // 優(yōu)先級高的排前面
    }
};

int main() {
    std::priority_queue<Task> pq;

    pq.push({1, 3});
    pq.push({2, 5});
    pq.push({3, 1});

    std::cout << "最高優(yōu)先級任務(wù) ID：" << pq.top().id << std::endl;  // 輸出 2

    pq.pop();
    std::cout << "新的最高優(yōu)先級任務(wù) ID：" << pq.top().id << std::endl;  // 輸出 1

    return 0;
}

? 特點(diǎn)

默認(rèn)是最大堆，因此 operator< 定義為優(yōu)先級小的在下面。

(2) 使用自定義比較函數(shù)

如果不能修改 struct，可以使用外部比較函數(shù)：

struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        return a.priority > b.priority;  // 最小堆
    }
};

std::priority_queue<Task, std::vector<Task>, CompareTask> pq;

完整示例：

#include <iostream>
#include <queue>

struct Task {
    int id;
    int priority;
};

// 使 priority_queue 變成最小堆
struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        return a.priority > b.priority;  // 小優(yōu)先級的任務(wù)優(yōu)先
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, CompareTask> pq;

    pq.push({1, 3});
    pq.push({2, 5});
    pq.push({3, 1});

    std::cout << "最高優(yōu)先級任務(wù) ID：" << pq.top().id << std::endl;  // 輸出 3

    pq.pop();
    std::cout << "新的最高優(yōu)先級任務(wù) ID：" << pq.top().id << std::endl;  // 輸出 1

    return 0;
}

? 適用場景

優(yōu)先隊(duì)列調(diào)度算法
事件驅(qū)動(dòng)仿真
A 搜索（最短路徑算法）*

5. priority_queue 適用場景

應(yīng)用場景	用法
最大堆（默認(rèn)）	std::priority_queue<int>
最小堆	std::priority_queue<int, std::vector<int>, std::greater<int>>
存儲(chǔ)結(jié)構(gòu)體（最大堆）	結(jié)構(gòu)體重載 <
存儲(chǔ)結(jié)構(gòu)體（最小堆）	std::greater<> 或自定義 Compare
K 大/小元素	維護(hù)大小為 K 的堆
Dijkstra / A 搜索*	結(jié)合 std::pair<int, int> 進(jìn)行路徑計(jì)算

6. 經(jīng)典應(yīng)用示例

(1) 找到前 K 個(gè)最大元素

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

void findTopK(std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // 最小堆

    for (int num : nums) {
        pq.push(num);
        if (pq.size() > k) pq.pop();  // 只保留 k 個(gè)最大值
    }

    std::cout << "前 " << k << " 個(gè)最大元素：" << pq.top() << std::endl;
}

int main() {
    std::vector<int> nums = {3, 1, 5, 12, 2, 11};
    findTopK(nums, 3);  // 輸出 5
}

? 復(fù)雜度：O(N log K)