C++優先キューの使用

転載先https://blog.csdn.net/u012804490/article/details/26241523優先キュー(priority queue)は、データ構造のスタックであり、コンピュータ科学における特殊なデータ構造の総称である.キューでは、スケジューラがキュー内の最初のジョブを繰り返し抽出して実行するため、実際には短い時間のタスクが終了するまで長い時間待つか、短くないが重要なジョブも優先権を持つ必要があります.優先キューは、このような問題を解決するために設計されたデータ構造です.優先キュー(スタック)は、通常、ツリーと見なすことができる配列オブジェクトです.
優先キューの共通関数:
Empty()優先キューが空の場合、真を返します.
pop()最初の要素を削除
push(x)要素xを追加
size()は、優先キューに存在する要素の数を返します.
トップ()は、優先キュー内で最も優先度の高い要素を返します.
例:

#include
#include
#include
using namespace std;
int main()
{
    int i;
    priority_queue<int> q;  //      
    //         
    q.push(4);    q.push(1);
    q.push(3);    q.push(5);
    q.push(6);    q.push(2);
    int len=q.size();    //             
    for(i=0;i// top()          
        //       ，      ，           
        printf("%d ",q.top()); 
        q.pop();   //        ，          
    }
    printf("
");
    if(q.empty())   //               
        printf("       
");
    return 0;
}

出力結果:6 5 4 3 1
この優先キューが空です.優先キューの小さな要素を優先してキューを出たい場合は、どうすればいいですか?
So easy!
priority_queue q;priority_に変更queue

#include
#include
#include
using namespace std;
int main()
{
    int i;
    priority_queue<int,vector<int>,greater<int> > q;
    //         
    q.push(4);    q.push(1);
    q.push(3);    q.push(5);
    q.push(6);    q.push(2);
    int len=q.size();    //             
    for(i=0;i// top()          
        //       ，      ，           
        printf("%d ",q.top()); 
        q.pop();   //        ，          
    }
    printf("
");
    if(q.empty())   //               
        printf("       
");
    return 0;
}

運転結果:1 2 3 4 5 6
優先キューが空です
greaterがlessになったここは検証しません.興味のある子供靴は自分で検証してください.
拡張:優先キューは、通常の配列の要素を優先キューの初期値に変換することもできます.
コードは次のとおりです.

#include  
#include  
#include  
using namespace std;  
int main()  
{  
    int a[6]={3,2,1,4,6,5};  
    priority_queue<int> q(a,a+6);  //               
    while(!q.empty())  
    {  
        printf("%d ",q.top());  
        q.pop();  
    }  
    printf("
");  
    return 0;  
}  

運転結果:6 5 4 3 2 1
コード2:

#include  
#include  
#include  
using namespace std;  
int main()  
{  
    int a[6]={3,2,1,4,6,5};  
    priority_queue<int> q(&a[2],a+6);  // &a[2]   a[2]        ，a+6           
    while(!q.empty())  
    {  
        printf("%d ",q.top());  
        q.pop();  
    }  
    printf("
");  
    return 0;  
}  

実行結果:6 5 4 1

優先度をカスタマイズし、データ型が基本データ型ではなく複雑なデータ型である場合は、operator()を再ロードする必要があります.

#include  
#include  
#include  
using namespace std;  
typedef struct  
{  
    int a;  
    int b;  
}Node;  
//         
struct cmp  
{  
    bool operator()(const Node &t1,const Node &t2)  
    {  
        return t1.b//    less，             
    }  
};  
int main()  
{  
    int i,n;  
    scanf("%d",&n);  
    Node *num=new Node[n];  
    for(i=0;iscanf("%d%d",&num[i].a,&num[i].b);  
    }  
    priority_queuevector,cmp> q(num,num+n);   //       
    while(!q.empty())  
    {  
        printf("%d ",q.top().b);  
        q.pop();  
    }  
    printf("
");  
    return 0;  
}  

入力:3
3 8
5 6
4 7
出力結果:
8 7 6