[자료구조] 우선순위 큐(priority queue) -C++

우선순위 큐

우선순위 큐(Priority Queue)는 각 요소에 우선순위가 할당된 큐 자료구조로 일반적으로 높은 우선순위를 가진 요소가 낮은 우선순위를 가진 요소보다 먼저 처리되는 큐이다. 우선순위 큐는 일반적인 큐와 달리 요소를 삽입할 때마다 요소의 우선순위를 기준으로 정렬되거나, 우선순위가 가장 높은 요소가 항상 먼저 나오도록 구현된다.

Q. ⭐️Queue와 priority Queue의 차이 비교

Queue 자료구조는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 구조로 저장하는 형식이다. 이와 달리 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.
시간 복잡도:

• Queue: enqueue->O(1), dequeue->O(1)
• priority queue: push->O(logn), pop-> O(logn)

c++에서의 우선순위 큐

1. 큐 헤더파일

c++에서는 우선순위 큐 priority_queue를 queue헤더 파일에서 제공한다.

#include<queue>

2. 우선순위 큐 생성

priority_queue<T> pq;

queue를 생성하듯이 다음처럼 우선순위 큐를 생성할 수 있다.
T에는 정수, char 등의 기본 자료형과 struct, class 등도 올 수 있다.

C++의 우선순위 큐는 기본적으로 Max heap 으로 설정되어 있다.
-> 즉 Max heap에서는 큰 값이 우선 순위가 큰 것 처럼 우선순위 큐도 큰 값의 우선순위가 높은 것이 default 이다.
내림차순이 기본

반대로 Min heap의 형태로 우선순위 큐를 설정하려면

이제 반대로 Min Heap으로 동작하도록 설정하고 싶다면, greater<int>를 사용하면 된다. 그러면 작은 값이 우선순위가 높아져 오름차순으로 정렬된다.

정렬 기준을 임의로 바꿔야하는 경우 축약한 선언은 불가하며, 아래와 같이 필요한 값들을 전부 넣어서 선언해야 한다.

#include <queue>
#include <vector>

using namespace std;

int main() {
    // Min Heap으로 동작하는 우선순위 큐
    priority_queue<int, vector<int>, greater<int>> pq; // 작은 값이 우선순위가 높음

    pq.push(90);
    pq.push(70);
    pq.push(85);

    // 작은 값이 우선순위가 높으므로, 70이 가장 우선순위가 높음
    // 따라서 top() 메서드를 사용하면 70이 출력됨
    cout << pq.top() << endl; // 출력: 70

    return 0;
}

T에 pair을 넣는 경우

우선순위 큐에 pair가 들어가게 작성해야 할 경우가 있다면 다음과 같이 작성할 수 있다. T에 pair<int, int>를 작성

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

using namespace std;

int main() {
    // pair<int, int>가 들어가는 Max Heap 우선순위 큐
    priority_queue<pair<int, int>> maxHeap;

    // pair<int, int>에는 첫 번째 값이 우선순위가 된다
    // 따라서, (우선순위, 값) 형태로 pair를 넣어준다.

    // 시험 점수들을 pair로 묶어서 넣어봅시다.
    maxHeap.push({90, 1});
    maxHeap.push({70, 2});
    maxHeap.push({85, 3});

    // pair의 첫 번째 값이 우선순위이므로, (90, 1)이 가장 우선순위가 높음
    // 따라서 top() 메서드를 사용하면 (90, 1)이 출력됨
    cout << "(" << maxHeap.top().first << ", " << maxHeap.top().second << ")" << endl; // 출력: (90, 1)

    return 0;
}

우선순위 큐 기본 함수

데이터 추가 .push
큐이름.push(데이터) 로 데이터 추가

pq.push(2);

데이터 삭제 .pop
큐이름.pop(데이터) 로 데이터 삭제

pq.pop(2);

첫번째 데이터 반환 .front
큐이름.front() 로 큐의 첫번째 데이터 반환

pq.front();

마지막 데이터 반환 .back
큐이름.back() 로 큐의 마지막 데이터 반환

pq.back();

큐 사이즈 반환 .size
큐이름.size() 로 큐의 현재 사이즈 반환

pq.size();

비었는지 확인 .empty
큐이름.empty() 로 큐가 비어있는지 확인

pq.empty();

두 큐의 내용 바꾸기 .swap
큐이름.swap() 로 큐의 내용을 서로 바꿔준다.

pq.swap(queue1,queue2);