c++ - Min stl priority_queue を作成するにはどうすればよいですか?

Question

デフォルトの stl プライオリティ キューは Max キューです (Top 関数は最大の要素を返します)。

簡単にするために、これは int 値のプライオリティ キューであるとします。

Answer 1

std::greater比較関数として使用:

std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;

Answer 2

1 つの方法は、優先度が逆になるように、通常の優先度キューを操作するための適切なコンパレータを定義することです。

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

 struct compare  
 {  
   bool operator()(const int& l, const int& r)  
   {  
       return l > r;  
   }  
 };  

 int main()  
 {  
     priority_queue<int,vector<int>, compare > pq;  

     pq.push(3);  
     pq.push(5);  
     pq.push(1);  
     pq.push(8);  
     while ( !pq.empty() )  
     {  
         cout << pq.top() << endl;  
         pq.pop();  
     }  
     cin.get();  
 }

それぞれ1、3、5、8を出力します。

STL とSedgewick の実装を介してプライオリティ キューを使用するいくつかの例をここに示します。

Answer 3

の3番目のテンプレートパラメータpriority_queueはコンパレータです。を使用するように設定しますgreater。

例えば

std::priority_queue<int, std::vector<int>, std::greater<int> > max_queue;

が必要#include <functional>になりstd::greaterます。

Answer 4

C++11 では、利便性のためにエイリアスを作成することもできます。

template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;

そして、次のように使用します。

min_heap<int> my_heap;

Answer 5

この問題を解決する 1 つの方法は、priority_queue 内の各要素の否定をプッシュして、最大の要素が最小の要素になるようにすることです。ポップ操作を行う際は、各要素の否定を取ります。

#include<bits/stdc++.h>
using namespace std;

int main(){
    priority_queue<int> pq;
    int i;

// push the negative of each element in priority_queue, so the largest number will become the smallest number

    for (int i = 0; i < 5; i++)
    {
        cin>>j;
        pq.push(j*-1);
    }

    for (int i = 0; i < 5; i++)
    {
        cout<<(-1)*pq.top()<<endl;
        pq.pop();
    }
}

Answer 6

値に -1 を掛け、最大ヒープを使用して最小ヒープの効果を得る