深入分析priority_queue的用法

一、什麼是priority_queue

priority_queue（優先隊列）是C++ STL中的一個容器，它是一個支持快速取出最大/最小元素的隊列，底層使用大根堆/小根堆實現。priority_queue封裝了heap的基本操作，包括push、pop、top等。priority_queue支持自定義比較器（仿函數）來實現自定義的元素比較方式。

二、基本用法

使用priority_queue需要包含頭文件。priority_queue使用方法類似於普通隊列，只是在創建時可以設置元素類型和比較器類型（默認使用less模板類來定義比較器，即小根堆）。

//創建int類型小根堆優先隊列
priority_queue pq;
//創建int類型大根堆優先隊列
priority_queue<int, vector, greater> pq;

以上代碼分別創建了一個int類型的小根堆和一個int類型的大根堆。在插入元素時，使用push操作在隊列尾部插入一個元素。而取出隊列中的最大/最小元素，可以使用top操作獲取隊列頭部（此時是最大/最小元素）的引用，並可以使用pop操作將最大/最小元素從隊列中取出。

//插入元素
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(1);
//獲取隊列頭部元素
int top_element = pq.top(); //1
//彈出隊列頭部元素
pq.pop();

三、自定義比較器

如果插入到priority_queue中的元素不是int類型，或者希望以一種非默認的方式進行元素比較，則可以定義自己的比較器。比較器是一個仿函數，其重載了()運算符，用於比較兩個元素的大小，返回bool類型的結果。

以一個結構體為例，假設需要按照結構體中的一個整型成員變量的值從小到大排序，則可以定義比較器如下：

struct Node{
    int val;
    Node(int v) : val(v) {}
};
struct myComparator {
    bool operator() (const Node& n1, const Node& n2) const {
        return n1.val > n2.val;
    }
};
priority_queue<Node, vector, myComparator> pq;

在以上示例中，定義了一個Node類型的小根堆優先隊列，同時指定了比較器myComparator用於存儲和取出元素時的大小判斷。在myComparator中重載了()運算符，其中定義了比較規則，這裡定義了n1.val > n2.val表示按照Node結構體中的val成員變量進行從小到大排序。

四、擴展應用

priority_queue還有很多其他的應用場景。例如，可以將優先隊列作為一種數據結構，利用其快速取出最大/最小元素的特性解決很多問題。

例如，可以用優先隊列實現topK問題，即在一堆數中找出前K大/小的數。具體實現方式是，先將前K個數插入到優先隊列中，然後遍歷剩下的數，如果當前數比隊列頭部元素小，則不做任何操作，否則將隊列頭部元素彈出並插入當前數。最後，隊列中剩下的元素就是前K大/小的數。

//求出前K小的數
vector findKthSmallest(vector& nums, int k) {
    priority_queue pq;
    for (int i = 0; i < k; i++) {
        pq.push(nums[i]);
    }
    for (int i = k; i < nums.size(); i++) {
        if (nums[i] < pq.top()) {
            continue;
        }
        pq.pop();
        pq.push(nums[i]);
    }
    vector res;
    while (!pq.empty()) {
        res.push_back(pq.top());
        pq.pop();
    }
    return res;
}

五、小結

本文重點介紹了priority_queue的用法，包括創建、插入、彈出、獲取隊列頭部元素以及自定義比較器的實現方式。同時，還介紹了priority_queue在實際開發中的應用場景，例如用於topK問題。