Dual-Priority-Queue

LixFlora·2022년 11월 15일

공부

목록 보기

3/7

우선순위큐를 응용하여 최소값과 최대값을 동시에 다루는 방법을 알아보겠습니다.

개념

우선순위큐를 두 개를 만들고, 인덱스를 통하여 하나처럼 다룹니다.
Pop 할 때 유효한 데이터인지 확인합니다.

구조

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minPQ;
priority_queue<pair<int, int>> maxPQ;
vector<int> isAlive;
int cnt = 0;

최대값을 반환하는 maxPQ와, 최소값을 반환하는 minPQ를 만들어둡니다.
isAlive 벡터를 만들어두고 유효한 값인지 저장합니다.
우선순위큐를 pair로 구성하고 second에는 isAlive의 인덱스값을 주도록 할 것입니다.

Push

minPQ.push(make_pair(x, cnt));
maxPQ.push(make_pair(x, cnt));
isAlive.push_back(1);
cnt++;

양쪽 모두에 push하도록 합니다.

Max 값

if(!maxPQ.empty()) {
    maxPQ.top().first; // Max 값
}
else {
    0; // 비어있음
}

Min 값

if(!minPQ.empty()) {
    minPQ.top().first; // Min 값
}
else {
    0; // 비어있음
}

Max Pop

if(!maxPQ.empty()) {
    isAlive[maxPQ.top().second] = 0;
    maxPQ.pop();
    while(!maxPQ.empty() && !isAlive[maxPQ.top().second]) {
        maxPQ.pop();
    }
    while(!minPQ.empty() && !isAlive[minPQ.top().second]) {
        minPQ.pop();
    }
}

maxPQ의 top의 isAlive 값을 0으로 변경하고, pop을 진행합니다.
그리고 다음 top의 isAlive를 검사하여 유효하지 않다면 pop합니다.
minPQ에 대해서도 마찬가지입니다.

Min Pop

if(!minPQ.empty()) {
    isAlive[minPQ.top().second] = 0;
    minPQ.pop();
    while(!maxPQ.empty() && !isAlive[maxPQ.top().second]) {
        maxPQ.pop();
    }
    while(!minPQ.empty() && !isAlive[minPQ.top().second]) {
        minPQ.pop();
    }
}