How can I create Min stl priority queue

Question

The default stl priority queue is a Max one  Top function returns the largest element    Say  for simplicity  that it is a priority queue of int values

User · Answer

The third template parameter for priority queue is the comparator  Set it to use greater   e g   std  priority queue lt int  std  vector lt int gt   std  greater lt int gt   gt  max queue    You ll need  include  lt functional gt  for std  greater

User · Answer

You can do it in multiple ways  1  Using greater as comparison function       include  lt bits stdc   h gt   using namespace std   int main         priority queue lt int vector lt int gt  greater lt int gt   gt pq      pq push 1       pq push 2       pq push 3        while  pq empty                  int r   pq top            pq pop            cout lt  lt r lt  lt                 return 0      2  Inserting values by changing their sign  using minus  -  for positive number and using plus     for negative number     int main         priority queue lt int gt pq2      pq2 push -1     for  1     pq2 push -2     for  2     pq2 push -3     for  3     pq2 push 4      for -4      while  pq2 empty                  int r   pq2 top            pq2 pop            cout lt  lt -r lt  lt                 return 0      3  Using custom structure or class     struct compare       bool operator   const int  amp  a  const int  amp  b                return a gt b            int main          priority queue lt int vector lt int gt  compare gt  pq      pq push 1       pq push 2       pq push 3        while  pq empty                  int r   pq top            pq pop            cout lt  lt r lt  lt                 return 0      4  Using custom structure or class you can use priority queue in any order     Suppose  we want to sort people in descending order according to their salary and if tie then according to their age       struct people               int age salary              struct compare      bool operator   const people  amp  a  const people  amp  b                        if a salary  b salary                                return a age gt b age                            else                               return a salary gt b salary                                  int main                  priority queue lt people vector lt people gt  compare gt  pq          people person1 person2 person3          person1 salary 100          person1 age   50          person2 salary 80          person2 age   40          person3 salary   100          person3 age 40            pq push person1           pq push person2           pq push person3            while  pq empty                          people r   pq top                pq pop                cout lt  lt r salary lt  lt     lt  lt r age lt  lt endl           Same result can be obtained by operator overloading     struct people   int age salary   bool operator lt   const people  amp  p const       if salary  p salary                return age gt p age            else               return salary gt p salary              In main function     priority queue lt people gt  pq  people person1 person2 person3  person1 salary 100  person1 age   50  person2 salary 80  person2 age   40  person3 salary   100  person3 age 40    pq push person1   pq push person2   pq push person3    while  pq empty          people r   pq top        pq pop        cout lt  lt r salary lt  lt     lt  lt r age lt  lt endl

User · Answer

One way would be to define a suitable comparator with which to operate on the ordinary priority queue  such that its priority gets reversed     include  lt iostream gt      include  lt queue gt     using namespace std      struct compare           bool operator   const int amp  l  const int amp  r                  return l  gt  r                   int main               priority queue lt int vector lt int gt   compare  gt  pq          pq push 3          pq push 5          pq push 1          pq push 8          while    pq empty                         cout  lt  lt  pq top    lt  lt  endl             pq pop                    cin get           Which would output 1  3  5  8 respectively   Some examples of using priority queues via STL and Sedgewick s implementations are given here

User · Answer

One Way to solve this problem is  push the negative of each element in the priority queue so the largest element will become the smallest element  At the time of making pop operation  take the negation of each element    include lt bits stdc   h gt  using namespace std   int main        priority queue lt int gt  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  lt  5  i                  cin gt  gt j          pq push j -1              for  int i   0  i  lt  5  i                  cout lt  lt  -1  pq top   lt  lt endl          pq pop

User · Answer

We can do this using several ways   Using template comparator parameter      int main                priority queue lt int  vector lt int gt   greater lt int gt   gt  pq         pq push 40         pq push 320         pq push 42         pq push 65         pq push 12          cout lt  lt pq top   lt  lt endl        return 0          Using used defined compartor class       struct comp                bool operator     int lhs  int rhs                       return lhs  gt  rhs                         int main                priority queue lt int  vector lt int gt   comp gt  pq          pq push 40          pq push 320          pq push 42          pq push 65          pq push 12           cout lt  lt pq top   lt  lt endl          return 0

User · Answer

Use std  greater as the comparison function   std  priority queue lt int  std  vector lt int gt   std  greater lt int gt   gt  my min heap

User · Answer

Multiply values with -1 and use max heap to get the effect of min heap

User · Answer

In C  11 you could also create an alias for convenience   template lt class T gt  using min heap   priority queue lt T  std  vector lt T gt   std  greater lt T gt  gt     And use it like this   min heap lt int gt  my heap

User · Answer

Based on above all answers I created an example code for how to create priority queue  Note  It works C  11 and above compilers   include  lt iostream gt   include  lt vector gt   include  lt iomanip gt   include  lt queue gt   using namespace std      template for prirority Q template lt class T gt  using min heap   priority queue lt T  std  vector lt T gt   std  greater lt T gt  gt   template lt class T gt  using max heap   priority queue lt T  std  vector lt T gt  gt    const int RANGE   1000   vector lt int gt  get sample data int size    int main      int n    cout  lt  lt   Enter number of elements N       cin  gt  gt  n    vector lt int gt  dataset   get sample data n      max heap lt int gt  max pq    min heap lt int gt  min pq        Push data to Priority Queue   for int i  dataset       max pq push i       min pq push i          while  max pq empty    amp  amp   min pq empty         cout  lt  lt  setw 10   lt  lt  min pq top   lt  lt         lt  lt  max pq top    lt  lt  endl      min pq pop        max pq pop             vector lt int gt  get sample data int size     srand time NULL      vector lt int gt  dataset    for int i 0  i lt size  i         dataset push back rand   RANGE         return dataset      Output of Above code   Enter number of elements N   4          33   535         49   411        411   49        535   33

[c++] How can I create Min stl priority_queue?

Examples related to c++

Examples related to stl

Examples related to priority-queue