【c++STL——第七講】priority_queue系列 (常用知識點總結)

文章目錄

• ​​一、前言​​
• ​​二、priority_queue的初始化​​
• ​​三、priority_queue的常用函數​​
• ​​四、priority_queue 自定義結構體初始化​​
• ​​最後​​

一、前言

優先隊列和隊列特性不同：按優先級排序 和 擷取

既然是​​​隊列​​​那麼先要包含頭檔案​

​#include <queue>​

​​, 他和​

​queue​

​​不同的就在于我們可以自定義其中資料的​​優先級​​, 讓優先級高的排在隊列前面,優先出隊

​​優先隊列​​​具有隊列的所有特性，包括基本操作，隻是在這基礎上​

​添加了内部的一個排序​

​​，它本質是一個​

​堆​

​​實作的

是以它的功能強大在哪裡呢？

四個字：​​

​自動排序​

​

二、priority_queue的初始化

這裡是預設的優先隊列（​

​非結構體結構​

​）

注意：預設是大根堆！！！

大根堆：priority_queue <類型> 變量名;

小根堆：priority_queue <類型,vecotr <類型>,greater <類型> > 變量名

如：
priority_queue<int, vector<int>, less<int> >s;//less表示按照遞減(從大到小)的順序插入元素
priority_queue<int, vector<int>, greater<int> >s;//greater表示按照遞增（從小到大）的順序插入元素

//注意後面兩個“>”不要寫在一起，“>>”是右移運算符      

​

​預設優先隊列樣例​

​

#include <iostream>
#include<queue>
using namespace std;
//priority_queue <int> q;預設大根堆 
priority_queue<int, vector<int>, less<int> >q1; //大根堆 
priority_queue<int, vector<int>, greater<int> >q2;//小根堆 
int a[5]={9,5,2,7,1}; 
int main()
{
    for(int i=0;i<5;i++)
   {
      q1.push(a[i]);
      q2.push(a[i]);
   }
    //大根堆 
     cout<<"大根堆:";
   while(!q1.empty())
   {
   cout<<q1.top()<<" ";
   q1.pop();
    }   
    cout<<endl;
    //小根堆
    cout<<"小根堆:";
    while(!q2.empty())
   {
   cout<<q2.top()<<" ";
   q2.pop();
    }   
}      

​

​輸出​

​

大根堆:9 7 5 2 1

小根堆:1 2 5 7 9

三、priority_queue的常用函數

size(); 這個堆的長度

    empty(); 傳回這個堆是否為空

    push();往堆裡插入一個元素

    top(); 傳回堆頂元素

    pop(); 彈出堆頂元素

    注意：堆沒有clear函數！！！
    注意：堆沒有back()函數！！！      

四、priority_queue 自定義結構體初始化

​

​自定義結構體實作大根堆，小根堆​

​

#include<iostream>
#include<queue>
using namespace std;

struct cmp1 {
   bool operator ()( int a ,int b ) {
      return a<b;
   }
};
struct cmp2 {
   bool operator ()( int  a ,int b ) {
      return a>b;
   }
};
int a[5]={9,5,2,7,1}; 
int  main() {

      priority_queue < int , vector<int> , cmp1  > q1;//從大到小 
      priority_queue < int , vector<int> , cmp2  > q2;//從小到大 

     for(int i=0;i<5;i++)
   {
      q1.push(a[i]);
      q2.push(a[i]);
   }

 //大根堆 
     cout<<"大根堆:";
   while(!q1.empty())
   {
   cout<<q1.top()<<" ";
   q1.pop();
    }   
    cout<<endl;
    //小根堆
    cout<<"小根堆:";
    while(!q2.empty())
   {
   cout<<q2.top()<<" ";
   q2.pop();
    }   
   return 0;
}      

​

​輸出​

​​ 大根堆:9 7 5 2 1

小根堆:1 2 5 7 9

​

​自定義結構體實作兩個成員x和y，按x小者優先​

​

#include <iostream>
#include<queue>
using namespace std;
struct node
{
  int x,y;
  bool operator < (const node & a) const
  {
    return x<a.x;//大根 
  //  return x>a.x;//小根 
  }
};
priority_queue <node> q;
int a[5]={2,5,1,6,4};
int b[5]={9,8,2,1,3};
int main()
{
  node t;
  for(int i=0;i<5;i++)
  {
    t.x=a[i];
    t.y=b[i];
    q.push(t);
  }
  while(!q.empty())
  {
    node m=q.top(); q.pop();
    cout<<m.x<<" "<<m.y<<endl;
  }
}      

​

​輸出​

​​ 6 1

5 8

4 3

2 9

1 2

​

​自定義結構體先按x升序，x相等時，再按y升序​

​

#include <iostream>
#include <queue>
using namespace std;
struct Node{
    int x, y;
    Node( int a= 0, int b= 0 ):
      x(a), y(b) {}
};
struct cmp{//重寫的仿函數
    bool operator() ( Node a, Node b ){//預設是less函數
        //傳回true時，a的優先級低于b的優先級（a排在b的後面）
        if( a.x== b.x ) return a.y> b.y;      
        return a.x> b.x; }
};
int main(){                        //仿函數替換預設比較方式
    priority_queue<Node, vector<Node>, cmp> q;
    
    for( int i= 0; i< 10; i++ )
    q.push( Node( rand()%10, rand()%10 ) );
    
    while( !q.empty() ){
        cout << q.top().x << ' ' << q.top().y << endl;
        q.pop();
    }
    return 0;
}      

​

​輸出​

​​ 0 4

1 1

2 5

4 2

4 9

5 5

6 7

7 1

7 1

8 8

​

​更深一點的，還在學習~​

​

最後

莫言真理無窮盡，寸進自有寸進歡