快捷導(dǎo)航

C++中的priority_queue容器使用及說明

更新時間：2026年04月10日 08:51:01 作者：你的冰西瓜

文章主要介紹了C++標(biāo)準(zhǔn)模板庫中的優(yōu)先級隊列(priority_queue)的功能、實現(xiàn)原理、使用方法及應(yīng)用場景,優(yōu)先級隊列提供按優(yōu)先級排序的數(shù)據(jù)存儲方式,默認為最大堆實現(xiàn),通過分析其構(gòu)造函數(shù)、操作函數(shù)、性能考慮等內(nèi)容,展示了優(yōu)先級隊列在實際應(yīng)用中的優(yōu)勢與注意事項

1.priority_queue概述

priority_queue是C++標(biāo)準(zhǔn)模板庫(STL)中的容器適配器，提供優(yōu)先級隊列功能。它保證優(yōu)先級最高的元素總是位于隊列前端，默認情況下是最大堆實現(xiàn)（最大元素優(yōu)先）。

2. 基本特性

優(yōu)先級排序：元素按優(yōu)先級排序，默認最大元素在前
容器適配器：基于其他序列容器實現(xiàn)（默認vector）
限制訪問：只允許訪問頂部元素
高效操作：插入和刪除操作時間復(fù)雜度為O(log?2n)O(\log_2 n)O(log2?n)
堆結(jié)構(gòu)：底層使用堆數(shù)據(jù)結(jié)構(gòu)實現(xiàn)

3. 頭文件與聲明

#include <queue>  // 注意：priority_queue也在<queue>頭文件中
using namespace std;

priority_queue<int> pq1;  // 默認最大堆，基于vector
priority_queue<int, vector<int>, greater<int>> pq2;  // 最小堆
priority_queue<string> pq3;

4. 構(gòu)造函數(shù)與初始化

4.1 默認構(gòu)造

priority_queue<int> pq;  // 創(chuàng)建空的最大堆

4.2 基于比較函數(shù)構(gòu)造

// 自定義比較函數(shù)
struct Compare {
    bool operator()(int a, int b) {
        return a > b;  // 最小堆
    }
};
priority_queue<int, vector<int>, Compare> custom_pq;

4.3 使用已有數(shù)據(jù)初始化

vector<int> vec = {3, 1, 4, 1, 5};
priority_queue<int> pq(vec.begin(), vec.end());  // 使用迭代器范圍構(gòu)造

5. 容量操作

5.1empty()

if (pq.empty()) {
    cout << "優(yōu)先級隊列為空";
}

5.2size()

cout << "優(yōu)先級隊列大小: " << pq.size();

6. 元素訪問

6.1top()

if (!pq.empty()) {
    cout << "最高優(yōu)先級元素: " << pq.top();
}

7. 修改操作

7.1push()

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

7.2emplace()

pq.emplace(15);  // 原地構(gòu)造元素(避免拷貝)

7.3pop()

if (!pq.empty()) {
    pq.pop();  // 移除最高優(yōu)先級元素
}

7.4swap()(C++11)

priority_queue<int> pq2;
pq.swap(pq2);  // 交換兩個優(yōu)先級隊列

8. 完整示例

#include <iostream>
#include <queue>
#include <vector>
#include <functional>  // 用于greater<int>
using namespace std;

int main() {
    // 最大堆示例
    priority_queue<int> max_heap;
    max_heap.push(30);
    max_heap.push(10);
    max_heap.push(50);
    max_heap.emplace(20);
    
    cout << "最大堆元素: ";
    while (!max_heap.empty()) {
        cout << max_heap.top() << " ";
        max_heap.pop();
    }
    cout << endl;
    
    // 最小堆示例
    priority_queue<int, vector<int>, greater<int>> min_heap;
    min_heap.push(30);
    min_heap.push(10);
    min_heap.push(50);
    min_heap.emplace(20);
    
    cout << "最小堆元素: ";
    while (!min_heap.empty()) {
        cout << min_heap.top() << " ";
        min_heap.pop();
    }
    cout << endl;
    
    // 自定義比較函數(shù)示例
    struct Point {
        int x, y;
        Point(int x, int y) : x(x), y(y) {}
        bool operator<(const Point& other) const {
            return (x*x + y*y) < (other.x*other.x + other.y*other.y);
        }
    };
    
    priority_queue<Point> point_pq;
    point_pq.emplace(1, 2);
    point_pq.emplace(3, 4);
    point_pq.emplace(0, 1);
    
    cout << "按與原點的距離排序的點: ";
    while (!point_pq.empty()) {
        Point p = point_pq.top();
        cout << "(" << p.x << "," << p.y << ") ";
        point_pq.pop();
    }
    cout << endl;
    
    return 0;
}

9. 底層容器與比較函數(shù)

9.1 底層容器選擇

priority_queue可以基于以下容器實現(xiàn)：

vector（默認）：隨機訪問性能好，適合堆操作
deque：兩端操作高效，但內(nèi)存使用不如vector緊湊

9.2 比較函數(shù)

less<T>（默認）：最大堆，大元素優(yōu)先
greater<T>：最小堆，小元素優(yōu)先
自定義比較函數(shù)：實現(xiàn)復(fù)雜排序邏輯

// 自定義比較函數(shù)示例：按字符串長度排序
struct LengthCompare {
    bool operator()(const string& a, const string& b) {
        return a.length() < b.length();  // 長度大的優(yōu)先
    }
};
priority_queue<string, vector<string>, LengthCompare> length_pq;

10. 實際應(yīng)用示例

10.1 合并KKK個有序鏈表

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct CompareNode {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;  // 最小堆
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, CompareNode> pq;
    
    for (auto node : lists) {
        if (node) pq.push(node);
    }
    
    ListNode dummy(0);
    ListNode* tail = &dummy;
    
    while (!pq.empty()) {
        tail->next = pq.top();
        pq.pop();
        tail = tail->next;
        
        if (tail->next) {
            pq.push(tail->next);
        }
    }
    
    return dummy.next;
}

10.2 查找前KKK個高頻元素

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) freq[num]++;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    for (auto& [num, count] : freq) {
        pq.push({count, num});
        if (pq.size() > k) {
            pq.pop();
        }
    }
    
    vector<int> result;
    while (!pq.empty()) {
        result.push_back(pq.top().second);
        pq.pop();
    }
    
    return result;
}

11. 性能考慮

時間復(fù)雜度：

push(): O(log?2n)O(\log_2 n)O(log2?n)
pop(): O(log?2n)O(\log_2 n)O(log2?n)
top(): O(1)O(1)O(1)
empty(): O(1)O(1)O(1)
size(): O(1)O(1)O(1)

空間復(fù)雜度：O(n)O(n)O(n)

底層容器選擇影響：

vector：內(nèi)存局部性好，通常性能更優(yōu)
deque：在某些情況下可能提供更好的性能

12. 注意事項

調(diào)用top()或pop()前必須檢查隊列是否為空
priority_queue不提供迭代器，無法遍歷內(nèi)部元素
自定義比較函數(shù)需要嚴格弱序
默認是最大堆，要創(chuàng)建最小堆需要顯式指定greater<T>

13. priority_queue與其他容器比較

特性	priority_queue	queue	set
排序方式	按優(yōu)先級	FIFO	按鍵值排序
訪問方式	僅頂部元素	隊首和隊尾	任意元素
插入復(fù)雜度	O(log?2n)O(\log_2 n)O(log2?n)	O(1)O(1)O(1)	O(log?2n)O(\log_2 n)O(log2?n)
刪除復(fù)雜度	O(log?2n)O(\log_2 n)O(log2?n)	O(1)O(1)O(1)	O(log?2n)O(\log_2 n)O(log2?n)
重復(fù)元素	允許	允許	不允許