우선순위 큐(priority_queue)

운영체제에서, 특정 프로세스의 실행 순서를 찾는 문제를 풀었다.
맨 앞 프로세스를 다른 프로세스들의 우선순위와 비교해서 가장 큰 우선순위면 실행, 아니라면 맨 뒤로 다시 넣는 방식이었다.

이 때 다른 사람이 max_element를 이용해서 우선순위를 비교했다.
하지만 이는 시간복잡도가 O(n)이며, 우선순위 큐를 사용하면 O(logn)이라는 사실을 알게 되었다.
그래서 이 방식에 대해 정리해보고자 한다.

---

우선순위 큐(Priority Queue)

우선순위 큐는 각 요소가 우선순위를 가지며, 큐에서 요소를 삽입하고 제거할 때 항상 가장 높은 우선순위를 가진 요소를 처리하는 자료구조이다. 일반적으로 힙(Heap) 구조를 기반으로 구현된다.

---

특징

1. 삽입과 삭제:

   • 삽입: 요소를 큐에 추가하며, 우선순위를 유지하도록 내부 구조를 조정한다.
   • 삭제: 우선순위가 가장 높은(또는 가장 낮은, 구현에 따라 다름) 요소를 제거한다.

2. 기본 동작:

   • C++의 priority_queue는 최대 힙(Max-Heap) 기반으로 동작한다.
     • 즉, 기본적으로 가장 큰 값이 우선순위가 높다.
   • 최소 힙(Min-Heap) 구현을 위해서는 반대 순서의 비교 함수를 사용한다.

3. 시간 복잡도:

   • 삽입(push): (O(log n))
   • 삭제(pop): (O(log n))
   • 최대값 접근(top): (O(1))

4. C++의 priority_queue 기본 구현:

   • 내부적으로 힙(heap) 자료구조(보통 std::vector와 std::make_heap)를 사용한다.

---

[예제 코드]

priority_queue (Max-Heap):

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq;

    pq.push(3); // 삽입
    pq.push(5);
    pq.push(1);

    cout << "최댓값: " << pq.top() << endl; // 최댓값 확인 (5)
    pq.pop(); // 최댓값 제거
    cout << "다음 최댓값: " << pq.top() << endl; // 3

    return 0;
}

Min-Heap 구현:

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

using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> min_pq;

    min_pq.push(3);
    min_pq.push(5);
    min_pq.push(1);

    cout << "최솟값: " << min_pq.top() << endl; // 최솟값 확인 (1)
    min_pq.pop(); // 최솟값 제거
    cout << "다음 최솟값: " << min_pq.top() << endl; // 3

    return 0;
}

---

우선순위 큐와 std::max_element의 차이

특징	우선순위 큐 (priority_queue)	std::max_element
용도	동적 데이터에서 최대/최소 값 관리	정적 데이터에서 최대 값 찾기
시간 복잡도	삽입/삭제: (O(log n))	(O(n))
사용 목적	실시간 데이터 추가/삭제 관리	한 번만 최댓값 찾기
구현 기반	힙 구조	선형 탐색
데이터 구조의 변화	삽입/삭제로 구조가 변함	데이터는 변하지 않음

---

언제 사용?

1. priority_queue:

   • 실시간으로 데이터의 최대/최소 값을 유지해야 할 때.
   • 데이터가 동적으로 삽입되고 삭제되는 경우.
   • (예: 다익스트라 알고리즘, 작업 스케줄링 등)

2. std::max_element:

   • 정적이고 변경되지 않는 데이터에서 최대값을 단 한 번만 구할 때.
   • 데이터 크기가 작거나 동적이지 않은 경우.

---

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> priorities, int location) {
    // 우선순위 큐 (내림차순)
    priority_queue<int> pq;
    queue<pair<int, int>> q; // {priority, index}
    
    // 초기화: 큐와 우선순위 큐에 값 넣기
    for (int i = 0; i < priorities.size(); i++) {
        pq.push(priorities[i]); // 중요도를 우선순위 큐에 삽입
        q.push({priorities[i], i}); // (중요도, 인덱스) 쌍으로 큐에 삽입
    }
    
    int order = 0; // 실행 순서를 저장
    
    // 프로세스 처리
    while (!q.empty()) {
        int cur_priority = q.front().first; // 현재 프로세스 중요도
        int cur_index = q.front().second;   // 현재 프로세스 인덱스
        q.pop(); // 큐에서 제거
        
        // 중요도가 가장 높은 경우 실행
        if (cur_priority == pq.top()) {
            pq.pop(); // 우선순위 큐에서도 제거
            order++; // 실행 순서 증가
            
            // 원하는 프로세스가 실행된 경우
            if (cur_index == location) {
                return order;
            }
        } else {
            // 중요도가 더 높은 프로세스가 있으면 다시 큐에 삽입
            q.push({cur_priority, cur_index});
        }
    }
    
    return -1; // 이론상 도달하지 않음
}

int main()
{...}

중요도와 인덱스를 map에 넣을 생각만 해봤는데, 큐에 넣으면 좋을 문제였다!