[c++] Min stl priority_queue를 어떻게 만들 수 있습니까?

기본 stl 우선 순위 큐는 최대 1입니다 (Top 함수는 가장 큰 요소를 반환합니다).

단순화를 위해 int 값의 우선 순위 큐라고 가정하십시오.



답변

사용 std::greater비교 함수로 :

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


답변

한 가지 방법은 우선 순위가 반전되도록 일반 우선 순위 대기열에서 작동 할 적절한 비교기를 정의하는 것입니다.

 #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 구현을 통해 우선 순위 대기열을 사용하는 몇 가지 예가 여기 에 나와 있습니다 .


답변

세 번째 템플릿 매개 변수 priority_queue는 비교 자입니다. 사용하도록 설정하십시오 greater.

예 :

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

당신은해야합니다 #include <functional>위해 std::greater.


답변

여러 가지 방법으로 할 수 있습니다.
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;
    }
  1. 연산자 오버로딩으로 동일한 결과를 얻을 수 있습니다.

    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;
    }

답변

C ++ 11에서는 편의를 위해 별칭을 만들 수도 있습니다.

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

다음과 같이 사용하십시오.

min_heap<int> my_heap;


답변

이 문제를 해결하는 한 가지 방법은 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();
    }
}


답변

위의 모든 답변을 바탕으로 우선 순위 대기열을 만드는 방법에 대한 예제 코드를 만들었습니다. 참고 : C ++ 11 이상 컴파일러에서 작동합니다.

#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>

using namespace std;

// template for prirority Q
template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;
template<class T> using max_heap = priority_queue<T, std::vector<T>>;

const int RANGE = 1000;

vector<int> get_sample_data(int size);

int main(){
  int n;
  cout << "Enter number of elements N = " ; cin >> n;
  vector<int> dataset = get_sample_data(n);

  max_heap<int> max_pq;
  min_heap<int> min_pq;

  // Push data to Priority Queue
  for(int i: dataset){
    max_pq.push(i);
    min_pq.push(i);
  }

  while(!max_pq.empty() && !min_pq.empty()){
    cout << setw(10) << min_pq.top()<< " | " << max_pq.top() << endl;
    min_pq.pop();
    max_pq.pop();
  }

}


vector<int> get_sample_data(int size){
  srand(time(NULL));
  vector<int> dataset;
  for(int i=0; i<size; i++){
    dataset.push_back(rand()%RANGE);
  }
  return dataset;
}

위 코드의 출력

Enter number of elements N = 4

        33 | 535
        49 | 411
       411 | 49
       535 | 33