如何创建Min stl priority_queue？

Question

默认的stl优先级队列是Max 1(Top函数返回最大的元素).

为简单起见,它说它是int值的优先级队列.

Answer 1

使用std::greater的比较函数:

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

Answer 2

一种方法是定义一个合适的比较器,用它来操作普通优先级队列,使其优先级反转:

 #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

第三个模板参数priority_queue是比较器.设置它使用greater.

例如

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

你需要#include <functional>的std::greater.

Answer 4

您可以通过多种方式执行此操作:
1.使用greater作为比较功能:

 #include <bits/stdc++.h>

using namespace std;

int main()
{
    priority_queue<int,vector<int>,greater<int> >pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);

    while(!pq.empty())
    {
        int r = pq.top();
        pq.pop();
        cout<<r<< " ";
    }
    return 0;
}

2.通过更改符号来插入值(使用减号( - )表示正数,使用加号(+)表示负数:

int main()
{
    priority_queue<int>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<<-r<<" ";
    }

    return 0;
}

3.使用自定义结构或类:

struct compare
{
    bool operator()(const int & a, const int & b)
    {
        return a>b;
    }
};

int main()
{

    priority_queue<int,vector<int>,compare> pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);

    while(!pq.empty())
    {
        int r = pq.top();
        pq.pop();
        cout<<r<<" ";
    }

    return 0;
}

4.使用自定义结构或类,您可以按任何顺序使用priority_queue.假设,我们希望根据他们的工资按降序对人进行排序,然后根据他们的年龄进行排序.

    struct people
    {
        int age,salary;

    };
    struct compare{
    bool operator()(const people & a, const people & b)
        {
            if(a.salary==b.salary)
            {
                return a.age>b.age;
            }
            else
            {
                return a.salary>b.salary;
            }

    }
    };
    int main()
    {

        priority_queue<people,vector<people>,compare> 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<<r.salary<<" "<<r.age<<endl;
    }

5. 运算符重载可以获得相同的结果:

   struct people
   {
   int age,salary;
   
   bool operator< (const people & p)const
   {
       if(salary==p.salary)
       {
           return age>p.age;
       }
       else
       {
           return salary>p.salary;
       }
   }};
   

   在主要功能:

   priority_queue<people> 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<<r.salary<<" "<<r.age<<endl;
   }
   

Answer 5

在C++ 11中,您还可以为方便起见创建别名:

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

并像这样使用它:

min_heap<int> my_heap;

Answer 6

解决这个问题的一种方法是,推动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();
    }
}