[C++系列] 61. priority_queue介紹使用及相關OJ

1. priority_queue的介紹和使用

1.1 priority_queue的介紹

1.優先隊列是一種容器擴充卡，根據嚴格的弱排序标準，它的第一個元素總是它所包含的元素中最大的。

2. 此上下文類似于堆，在堆中可以随時插入元素，并且隻能檢索最大堆元素(優先隊列中位于頂部的元素)。

3. 優先隊列被實作為容器擴充卡，容器擴充卡即将特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來通路其元素。元素從特定容器的“尾部”彈出，其稱為優先隊列的頂部。

4. 底層容器可以是任何标準容器類模闆，也可以是其他特定設計的容器類。容器應該可以通過随機通路疊代器通路，并支援以下操作：

• empty()：檢測容器是否為空
• size()：傳回容器中有效元素個數
• front()：傳回容器中第一個元素的引用
• push_back()：在容器尾部插入元素
• pop_back()：删除容器尾部元素

5.标準容器類vector和deque滿足這些需求。預設情況下，如果沒有為特定的priority_queue類執行個體化指定容器類，則使用vector。

6. 需要支援随機通路疊代器，以便始終在内部保持堆結構。容器擴充卡通過在需要時自動調用算法函數make_heap、push_heap和pop_heap來自動完成此操作。

1.2 priority_queue的使用

優先級隊列預設使用vector作為其底層存儲資料的容器(vector可以随機通路。雙端隊列：實體不連續，邏輯連續，也可以随機通路，但需要計算偏移量，)在vector上又使用了堆算法将vector中元素構造成堆的結構，是以priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用priority_queue。注意：預設情況下priority_queue是大堆。

函數聲明	接口說明
priority_queue(const Compare& x = Compare(), const Container& y = Container() );	構造一個空的優先級隊列
template priority_queue(InputIterator first, InputIterator last, const Compare& comp = Compare(), const Container& ctnr = Container());	用[first, last)區間中的元素構造優先級隊列
bool empty( ) const	檢測優先級隊列是否為空，是傳回true，否則傳回false
const value_type& top ( ) const	傳回優先級隊列中最大(最小元素)，即堆頂元素
void push ( const T& x )	在優先級隊列中插入元素x
void pop ( )	删除優先級隊列中最大(最小)元素，即堆頂元素

【注意】

1.預設情況下，priority_queue是大堆。

仿函數，以greater函數将priority_queue的預設大堆改變為小堆，再次貼上STL的核心結構：

#include <vector>
#include <queue>
#include <functional>   // greater算法的頭檔案
 
void TestPriorityQueue()
{
    // 預設情況下，建立的是大堆，其底層按照小于号比較
    vector<int> v{3,2,7,6,0,4,1,9,8,5};
    priority_queue<int> q1;
    for (auto& e : v)
        q1.push(e);
    cout << q1.top() << endl;
 
    // 如果要建立小堆，将第三個模闆參數換成greater比較方式
    // priority_queue有三個參數: 類型，容器擴充卡(預設使用vector)，仿函數(預設less，為大堆)，小堆采用greater仿函數即可
    // 模闆裡面一定傳的為類型，并且類型需要回調，則僅有重載()的仿函數能夠滿足要求
    priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
    cout << q2.top() << endl;
}
           

2.如果在priority_queue中放自定義類型的資料，使用者需要在自定義類型中提供>或<的重載

class Date
{
public:
    Date(int year = 1900, int month = 1, int day = 1)
        : _year(year)
        , _month(month)
        , _day(day)
    {}
 
    bool operator<(const Date& d)const
    {
        return (_year < d._year) ||
               (_year == d._year && _month < d._month) ||
               (_year == d._year && _month == d._month && _day < d._day);
    }
 
    bool operator>(const Date& d)const
    {
        return (_year > d._year) ||
            (_year == d._year && _month > d._month) ||
            (_year == d._year && _month == d._month && _day > d._day);
    }
 
    friend ostream& operator<<(ostream& _cout, const Date& d)
    {
        _cout << d._year << "-" << d._month << "-" << d._day;
        return _cout;
    }
 
private:
    int _year;
    int _month;
     int _day;
};
 
void TestPriorityQueue()
{
    // 大堆，需要使用者在自定義類型中提供<的重載
    priority_queue<Date> q1;
    q1.push(Date(2018, 10, 29));
    q1.push(Date(2018, 10, 28));
    q1.push(Date(2018, 10, 30));
    cout << q1.top() << endl;
 
    // 如果要建立小堆，需要使用者提供>的重載
    priority_queue<Date, vector<Date>, greater<Date>> q2;
    q2.push(Date(2018, 10, 29));
    q2.push(Date(2018, 10, 28));
    q2.push(Date(2018, 10, 30));
    cout << q2.top() << endl;
}
           

3.有些情況下，使用者可能需要提供比較器規則

class Less
{
public:
    bool operator()(const Date* pLeft, const Date* pRight)	// 需要重載小括号實作類型的回調
    {
        return *pLeft < *pRight;
    }
};
 
 
void TestPriorityQueue()
{
    // 自己定制比較的規則
    priority_queue<Date*, vector<Date*>, Less> q;
    q.push(&Date(2018, 10, 29));
    q.push(&Date(2018, 10, 28));
    q.push(&Date(2018, 10, 30));
    cout << *q.top() << endl;
    return 0;
}
           

1.3 priority_queue在OJ上的使用

1.3.1 數組中的第K個最大元素

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> p(nums.begin(), nums.end());
        // 将優先級隊列中前k-1個元素删除掉
        for (int i = 0; i < k - 1; ++i) {
            p.pop();
        }
        return p.top();
    }
};