[자료구조] 우선순위 큐(priority_queue)

※코딩뉴비가 자신이 이해한대로 쓴 글이라 정확하지 않은 정보가 담겨있을 수 있습니다.

우선순위 큐란?

자신이 정해놓은 우선순위대로 넣었던 원소가 나오는 자료구조

​

우선순위 큐의 구현

우선순위 큐는 주로 힙(Heap)이라는 자료 구조로 구현합니다. 왜일까요? 삽입과 삭제에 대한 효율이 좋기 때문입니다.

배열로 우선순위 큐를 구현할 경우, 우선순위에 따라서 배열을 정렬해놓아 사용할 수 있습다. 그러면 가장 우선순위가 높은 원소를 삭제할 때에는 가장 앞의 원소를 삭제하면 되므로 O(1)의 시간복잡도가 걸립니다. 다만, 삽입 과정에서 최악의 경우 모든 원소와 하나하나 비교해야 하기 때문에 O(N)의 시간복잡도가 걸립니다.

연결 리스트로도 비슷하게 생각할 때 삽입은 O(N), 삭제는 O(1)이 걸립니다.

​

그러나, 우선순위 큐를 힙으로 구현하면 삽입과 삭제가 모두 O(logN)만큼 걸리게 됩니다.

​

그러면 힙이란 무엇이고 어떻게 구현하는 것일까요?

다음 그림을 한 번 봅시다.

이 그림은 원소가 10개인 최소 힙입니다. 대충 봤을 때, 완전이진트리 구조인 것을 알 수 있습니다. 천천히 살펴보면, 부모 노드가 자식 노드보다 항상 작다는 것이 보입니다. 이것이 최소 힙의 기본입니다. 물론 최대 힙은 반대로 부모 노드가 자식 노드보다 항상 큽니다.

​

이제 힙을 구현해봅시다.

1-based의 경우, 이런 이진 트리 구조에서 부모의 인덱스가 n이라면, 자식의 인덱스가 2n과 2n+1이다. 자식의 인덱스가 n이라면 부모의 인덱스는 n/2로 표현할 수 있습니다.

​

삽입의 경우, 삽입할 원소를 힙의 가장 끝에 넣습니다. 그리고 그 노드와 그 노드의 부모 노드를 우선순위에 따라 비교해가며 그 노드가 우선순위가 더 높을 경우, 부모 노드와 그 노드를 swap합니다. 구현은 다음과 같습니다.

void ins(int x) {
    minheap[++n]=x;
    int i=n;
    while(i/2>0) {
        if(minheap[i]<minheap[i/2]) swap(minheap[i], minheap[i/2]);
        else break;
        i/=2;
    }
}

최대 힙은 부등호의 방향만 반대로 하면 됩니다.

 

삭제의 경우, 다음과 같은 순서에 따라 우선순위가 가장 높은 원소를 삭제하게 됩니다.

1. 인덱스가 1인 원소를 삭제한다.

2. 마지막 원소 X를 가장 앞으로 옮긴다.

3. X의 자식 노드 2개를 비교해 자식 노드 중 우선순위가 높은 것을 고른다(Y). Y가 X보다 우선순위가 높으면, X와 Y를 바꾼다.

4. 3을 반복한다.

코드는 다음과 같습니다.

int del() {
    if(!n) return 0;
    int p=minheap[1];
    minheap[1]=minheap[n];
    minheap[n--]=0;
    int i=1;
    while(1) {
        int s;
        if(2*i+1<=n) {
            if(minheap[2*i]>minheap[2*i+1]) s=2*i+1;
            else s=2*i;
            if(minheap[i]>minheap[s]) {
                swap(minheap[i], minheap[s]);
                i=s;
            }
            else break;
        }
        else if(2*i<=n) {
            if(minheap[i]>minheap[2*i]) {
                swap(minheap[i], minheap[2*i]);
                i*=2;
            }
            else break;
        }
        else break;
    }
    return p;
}

마찬가지로 최대 힙은 부등호 방향을 반대로 하면 됩니다.

​

앞에서 우선순위 큐를 구현해보았습니다. 그러나 우선순위 큐를 쓰는 문제에서 매번 이런 것을 하기에는 귀찮겠죠? 그래서 c++ STL에는 이미 우선순위 큐가 구현이 되어있습니다.

값이 더 큰 것을 우선순위가 높은 것으로 하고 싶다면(최대 힙) 다음과 같이 쓰면 됩니다.

priority_queue<int> pq;
pq.push(1); //pq에 1을 삽입
pq.top(); //pq에서 가장 큰 원소
pq.pop(); //pq에서 가장 큰 원소 삭제

값이 더 작은 것을 우선순위가 높은 것으로 하고 싶다면

priority_queue<int, vector<int>, greater<int>> pq;

와 같이 선언하면 됩니다.

 

우선순위 큐의 활용

우선순위 큐의 기본문제와 그 풀이입니다.(이때는 우선순위 큐가 STL에 있는지 몰랐던 때라 구현을 감안하고 봐주시면 좋겠습니다.)

최대 힙을 구현하는 문제: https://www.acmicpc.net/problem/11279

11279번: 최대 힙

#include <bits/stdc++.h>
using namespace std;
int a[100001], n;
void ins(int x) {
    a[++n]=x;
    int i=n;
    while(i/2>0) {
        if(a[i]>a[i/2]) swap(a[i], a[i/2]);
        else break;
        i/=2;
    }
}
int del() {
    if(!n) return 0;
    int p=a[1];
    a[1]=a[n];
    a[n--]=0;
    int i=1;
    while(1) {
        int s;
        if(2*i+1<=n) {
            if(a[2*i]<a[2*i+1]) s=2*i+1;
            else s=2*i;
            if(a[i]<a[s]) {swap(a[i], a[s]);i=s;}
            else break;
        }
        else if(2*i<=n) {
            if(a[i]<a[2*i]) {swap(a[i], a[2*i]);i*=2;}
            else break;
        }
        else break;
    }
    return p;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int x;
        cin >> x;
        if(x) ins(x);
        else cout << del() << "\n";
    }
}

최소 힙을 구현하는 문제: https://www.acmicpc.net/problem/1927

1927번: 최소 힙

#include <bits/stdc++.h>
using namespace std;
int a[100001], n;
void ins(int x) {
    a[++n]=x;
    int i=n;
    while(i/2>0) {
        if(a[i]<a[i/2]) swap(a[i], a[i/2]);
        else break;
        i/=2;
    }
}
int del() {
    if(!n) return 0;
    int p=a[1];
    a[1]=a[n];
    a[n--]=0;
    int i=1;
    while(1) {
        int s;
        if(2*i+1<=n) {
            if(a[2*i]>a[2*i+1]) s=2*i+1;
            else s=2*i;
            if(a[i]>a[s]) {swap(a[i], a[s]);i=s;}
            else break;
        }
        else if(2*i<=n) {
            if(a[i]>a[2*i]) {swap(a[i], a[2*i]);i*=2;}
            else break;
        }
        else break;
    }
    return p;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int x;
        cin >> x;
        if(x) ins(x);
        else cout << del() << "\n";
    }
}

절댓값과 그 수의 크기를 우선순위로 설정하여 푸는 문제: https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

풀이 ​

우선 순위를

1. 절댓값이 더 작은 것

2. 절댓값이 같다면 값이 더 작은 것

으로 설정해서 삽입과 삭제를 하면 된다.

#include <bits/stdc++.h>
using namespace std;
int a[100001], n;
int ab(int x) {
    if(x>0) return x;
    else return -x;
}
void ins(int x) {
    a[++n]=x;
    int i=n;
    while(i/2>0) {
        if(ab(a[i])<ab(a[i/2]) || (ab(a[i])==ab(a[i/2]) && a[i]<a[i/2])) swap(a[i], a[i/2]);
        else break;
        i/=2;
    }
}
int del() {
    if(!n) return 0;
    int p=a[1];
    a[1]=a[n];
    a[n--]=0;
    int i=1;
    while(1) {
        int s;
        if(2*i+1<=n) {
            if(ab(a[2*i])>ab(a[2*i+1]) || (ab(a[2*i])==ab(a[2*i+1]) && a[2*i]>a[2*i+1])) s=2*i+1;
            else s=2*i;
            if(ab(a[i])>ab(a[s]) || (ab(a[i])==ab(a[s]) && a[i]>a[s])) {swap(a[i], a[s]);i=s;}
            else break;
        }
        else if(2*i<=n) {
            if(ab(a[i])>ab(a[2*i]) || (ab(a[i])==ab(a[2*i]) && a[i]>a[2*i])) {swap(a[i], a[2*i]);i*=2;}
            else break;
        }
        else break;
    }
    return p;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int x;
        cin >> x;
        if(x) ins(x);
        else cout << del() << "\n";
    }
}

최소 힙과 최대 힙을 같이 써서 중앙값을 출력하는 문제: https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

풀이

중앙값을 N이라 하자. N보다 작은 원소는 maxHeap에, N보다 큰 원소는 minHeap에 저장될 것이다.

a라는 원소를 삽입한다고 하자. a와 N을 비교하여

a가 N보다 작으면

1. N보다 작은 원소가 N보다 큰 원소보다 적으면 그냥 a를 maxHeap에 넣으면 된다.

2. 둘의 원소의 개수가 같으면 N보다 작은 원소 중 가장 큰 원소가 중앙값이 되고(a 포함), N은 minHeap에 넣는다.

a가 N보다 클 때는 비슷하게 하면 된다.

#include <bits/stdc++.h>
using namespace std;
int minHeap[50002], maxHeap[50002], Nmin, Nmax;
void ins(bool k, int x) {
    if(k) {
        minHeap[++Nmin]=x;
        int i=Nmin;
        while(i/2) {
            if(minHeap[i]<minHeap[i/2]) swap(minHeap[i], minHeap[i/2]);
            else break;
            i/=2;
        }
    }
    else {
        maxHeap[++Nmax]=x;
        int i=Nmax;
        while(i/2) {
            if(maxHeap[i]>maxHeap[i/2]) swap(maxHeap[i], maxHeap[i/2]);
            else break;
            i/=2;
        }
    }
}
void del(bool k) {
    if(k) {
        minHeap[1]=minHeap[Nmin];
        minHeap[Nmin--]=0;
        int i=1;
        while(1) {
            if(2*i+1<=Nmin) {
                if(minHeap[2*i]>minHeap[2*i+1]) i=2*i+1;
                else i=2*i;
                if(minHeap[i]<minHeap[i/2]) swap(minHeap[i], minHeap[i/2]);
                else break;
            }
            else if(2*i<=Nmin) {
                if(minHeap[i]>minHeap[2*i]) {swap(minHeap[i], minHeap[i*2]);i=2*i;}
                else break;
            }
            else break;
        }
    }
    else {
        maxHeap[1]=maxHeap[Nmax];
        maxHeap[Nmax--]=0;
        int i=1;
        while(1) {
            if(2*i+1<=Nmax) {
                if(maxHeap[2*i]<maxHeap[2*i+1]) i=2*i+1;
                else i=2*i;
                if(maxHeap[i]>maxHeap[i/2]) swap(maxHeap[i], maxHeap[i/2]);
                else break;
            }
            else if(2*i<=Nmax) {
                if(maxHeap[i]<maxHeap[2*i]) {swap(maxHeap[i], maxHeap[i*2]);i=2*i;}
                else break;
            }
            else break;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, mid=10001;
    cin >> n;
    while(n--) {
        int x;
        cin >> x;
        if(mid==10001) mid=x;
        else {
            if(mid<x) {
                if(Nmin==Nmax) ins(1, x);
                else {
                    ins(0, mid);
                    if(x>minHeap[1]) {mid=minHeap[1];del(1);ins(1, x);}
                    else mid=x;
                }
            }
            else {
                if(Nmax+1==Nmin) ins(0, x);
                else {
                    ins(1, mid);
                    if(Nmax && x<maxHeap[1]) {mid=maxHeap[1];del(0);ins(0,x);}
                    else mid=x;
                }
            }
        }
        cout << mid << "\n";
    }
}

앞서 살펴본 경우는 우선순위 큐로 푸는 것임이 드러나는 문제들입니다.

그러나 우선순위 큐는 훨씬 더 활용 범위가 넓습니다.

예를 들어, 다익스트라 알고리즘 같은 경우에서 우선순위 큐를 사용하면 시간복잡도를 크게 줄일 수 있습니다.

 

감사합니다.