c++

• vector와 같은 컨테이너 adapter 중 하나
• 우선 순위에 맞춰 Queue를 정렬
• Queue에 값 저장 시 default가 내림차순 or 정의된 구조체 or 오름차순(greator 비교함수) 형태로 정렬
• 우선순위가 가장 높은 값이 top에 위치

#include <queue>
priority_queue<data_type> q1; // 내림차순에 따라 정렬 (default)
priority_queue<data_type, container, greater<data_type>> q2; // 오름차순(greater)에 따라 정렬
priority_queue<data_type, container, struct> q3; // 비교함수(사용자 정의 구조체)에 따라 정렬

언제사용? 힙(Heap)과 같은 자료구조 사용 시 //힙으로 구현 시 가장 효율적

• 힙(Heap)

💡Priority Queue의 멤버 함수

1. push(‘’) //원소 추가
2. pop() //맨 앞에 있는 원소 삭제
3. top() //맨 앞 원소 return (가장 처음에 들어온 원소)
4. empty() //큐가 비어있으면 true, 아니면 false
5. size() //큐의 사이즈 반환

구현 예시

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

struct cmp
{
    //절대값이 더 작은 값에 우선순위를 높게 줌
    bool operator()(int n1, int n2)
    {
        if (abs(n1) > abs(n2))
            return true;
        else if (abs(n1) == abs(n2))
        {
            if (n1 > n2)
                return true;
            else
                return false;
        }
        return false;
    }
};

int main(void)
{
    priority_queue<int, vector<int>, cmp> pq;
    pq.push(1);
    pq.push(-1); // -1 1
    pq.push(7);  // -1 1 7
    pq.push(-4); // -1 1 -4 7
    pq.pop();    // -1 빠짐
    pq.push(15); // 1 -4 7 15

    while (!pq.empty())
    {
        cout << pq.top() << ' ';
        pq.pop();
    }
    //출력 : 1 -4 7 15
    return 0;
}

#include <iostream>
#include <queue>
#include <functional>    // greater
using namespace std;
 
struct Student {
    int id;
    int math, eng;
    Student(int num, int m, int e) : id(num), math(m), eng(e) {}    // 생성자 정의

    // 그냥 점수에 상관 없이 학번기준 학번이 작은것이 Top 을 유지 한다
    bool operator<(const Student s) const {
        return this->id > s.id;
    }
};
 
int main() {
    priority_queue<Student> pq;  
 
    pq.push(Student(3, 100, 50));
    pq.push(Student(1, 60, 50));
    pq.push(Student(2, 80, 50));
    pq.push(Student(4, 90, 50));
    pq.push(Student(5, 70, 40));
    
// 학번을 기준으로 작은 것이 먼저 출력이 된다 그 이유는 구조체 내부의 연산자 오버로딩에 있다
    while (!pq.empty()) {
        Student ts = pq.top(); pq.pop();
        cout << "(학번, 수학 , 영어 ) : " << ts.id << ' ' << ts.math << ' ' << ts.eng << '\\n';
    }
 
    return 0;
}

//[출처]<https://kbj96.tistory.com/15>

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

int main() {
	
	priority_queue<pair<int,int>> temp; //key 값을 기준으로 최대값 우선순위 큐
	temp.push(make_pair(3,100));
	temp.push(make_pair(-2,140));
	temp.push(make_pair(3,50));
	temp.push(make_pair(49,12));
	temp.push(make_pair(300,-20));
	int sz = temp.size();
	for(int i=0;i<sz;i++){
		cout << temp.top().first << ',' << temp.top().second << '\\n';
		temp.pop();
	}
	
	return 0;
}
/* 출력결과
		300, -20
    49, 12
    3, 100
		3, 50
		-2, 140
*/
//[출처]<https://doorrock.tistory.com/13>