Comment créer Minstl priority_queue?

Question

La file d'attente par défaut de priorité stl est une file d'attente maximale (la fonction Top renvoie l'élément le plus grand).

Disons, pour simplifier, que c'est une file d'attente prioritaire de valeurs int.

Answer 1

Utilisez std::greater comme fonction de comparaison:

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

Answer 2

Une solution consisterait à définir un comparateur approprié avec lequel opérer sur la file d'attente à priorité ordinaire, de telle sorte que sa priorité soit inversée:

  #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();  
 }
 

Ce qui donnerait 1, 3, 5, 8 respectivement.

Quelques exemples d'utilisation de files d'attente prioritaires via STL et les implémentations de Sedgewick sont donnés ici .

Answer 3

Le troisième paramètre de modèle pour priority_queue est le comparateur. Configurez-le pour utiliser greater .

par exemple

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

Vous aurez besoin de #include <functional> pour std::greater .