우선순위 큐(priority_queue) 완전 정복하기
우선순위 큐는 2학년 자료구조와 3학년 컴퓨팅 문제와 알고리즘 수업에서 배웠던 자료구조다.
개념 자체는 여러 번 배웠지만 코딩테스트를 준비하면서 막상 C++로 사용하려고 하니 생각보다 헷갈리는 부분이 많았다.
특히 다음과 같은 코드가 등장했을 때였다.
priority_queue<int, vector<int>, greater<int>> pq;priority_queue까지는 알겠는데 갑자기 vector는 왜 등장하는 것이고, greater<int>는 또 무엇일까?
그리고 조금 더 생각해보니
우선순위 큐는 내부적으로 데이터를 어떻게 저장할까?
Heap은 정확히 무엇일까?
최대 힙과 최소 힙의 차이는 무엇일까?
Heap과 priority_queue는 같은 것일까?
queue 자체가 자료구조인데 왜 vector가 또 필요한 걸까?와 같은 질문들이 생겼다.
그래서 이번 기회에 단순히 priority_queue의 사용법만 외우는 것이 아니라
Queue
↓
Complete Binary Tree
↓
Heap
↓
Min Heap / Max Heap
↓
Heap의 데이터 저장 방식
↓
priority_queue
↓
Container / Container Adaptor
↓
Compare
↓
실제 알고리즘 활용까지 하나씩 연결해서 정리해보고자 한다.
먼저 Queue란 무엇일까?
우선순위 큐를 이해하기 전에 먼저 Queue라는 자료구조부터 알아보자.
Queue는 전형적인 FIFO(First In First Out) 구조를 가진 자료구조다.
말 그대로
먼저 들어온 데이터가 먼저 나간다.
라는 규칙을 가진다.
예를 들어 다음 순서로 데이터를 넣었다고 생각해보자.
10
20
30Queue에서는 가장 먼저 들어온 10이 가장 먼저 나온다.
입력
10 → 20 → 30
출력
10 → 20 → 30C++에서는 다음과 같이 사용할 수 있다.
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
cout << q.front(); // 10
q.pop();
cout << q.front(); // 20Queue에서 중요한 것은 데이터의 크기가 아니라 들어온 순서다.
그런데 모든 문제에서 먼저 들어온 데이터를 먼저 처리해야 하는 것은 아니다.
예를 들어 운영체제에서 작업을 처리한다고 생각해보자.
작업 A : 우선순위 1
작업 B : 우선순위 10
작업 C : 우선순위 5단순한 Queue라면 들어온 순서대로 처리해야 한다.
하지만 우선순위가 높은 작업을 먼저 처리해야 한다면 이야기가 달라진다.
작업 B
↓
작업 C
↓
작업 A처럼 삽입된 순서가 아니라 우선순위를 기준으로 데이터를 꺼내야 한다.
이러한 상황에서 사용할 수 있는 것이 Priority Queue, 즉 우선순위 큐다.
우선순위 큐(Priority Queue)란?
우선순위 큐는 각각의 데이터가 가지고 있는 우선순위에 따라 데이터를 꺼내는 자료구조다.
일반 Queue가
먼저 들어온 데이터
→ 먼저 꺼낸다.라는 규칙을 가진다면,
Priority Queue는
우선순위가 높은 데이터
→ 먼저 꺼낸다.라는 규칙을 가진다.
예를 들어
priority_queue<int> pq;
pq.push(20);
pq.push(10);
pq.push(100);을 실행했다고 해보자.
C++의 priority_queue는 기본적으로 큰 값의 우선순위가 높다.
따라서
cout << pq.top();의 결과는
100이다.
pop()을 수행한 후 다시 top()을 확인하면
20이 나온다.
따라서 꺼내는 순서는
100
↓
20
↓
10이 된다.
여기까지만 보면
"그냥 내부 데이터를 100, 20, 10 순서로 정렬해놓는 거 아닌가?"
라고 생각할 수 있다.
나도 처음에는 그렇게 생각했다.
하지만 우선순위 큐는 내부의 모든 데이터를 정렬해서 가지고 있는 자료구조가 아니다.
이를 이해하기 위해서는 먼저 Heap이라는 자료구조를 알아야 한다.
Heap이란?
우선순위 큐를 이해할 때 가장 중요한 개념 중 하나가 Heap이다.
Heap은 완전 이진 트리(Complete Binary Tree)를 기반으로 하면서 부모와 자식 사이에 특정한 순서 조건을 만족하는 자료구조다.
따라서 Heap을 이해하려면 먼저 완전 이진 트리가 무엇인지 알아야 한다.
완전 이진 트리(Complete Binary Tree)란?
이진 트리(Binary Tree)는 하나의 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리다.
10
/ \
20 30완전 이진 트리는 이진 트리 중에서도 마지막 레벨을 제외한 모든 레벨이 채워져 있고, 마지막 레벨의 노드는 왼쪽부터 차례대로 채워지는 형태를 말한다.
예를 들어 다음 트리는 완전 이진 트리다.
[완전 이진 트리 예시 이미지 삽입]
10
/ \
20 30
/ \ /
40 50 60마지막 레벨이 완전히 채워지지는 않았지만 왼쪽부터 순서대로 노드가 들어가 있다.
반면 다음과 같은 형태는 완전 이진 트리가 아니다.
[완전 이진 트리가 아닌 예시 이미지 삽입]
10
/ \
20 30
\ \
50 60중간에 비어 있는 공간이 존재하기 때문이다.
이러한 완전 이진 트리의 특징은 Heap을 배열과 같은 연속적인 구조로 효율적으로 표현할 수 있게 해준다.
트리를 배열에 저장할 수 있다고?
처음 Heap을 공부할 때 조금 신기했던 부분이다.
트리라고 하면 보통
Node
left pointer
right pointer같은 구조를 먼저 생각하게 된다.
하지만 완전 이진 트리는 노드가 왼쪽부터 빈 공간 없이 채워지기 때문에 배열에 순서대로 저장할 수 있다.
다음 트리를 생각해보자.
100
/ \
40 80
/ \ / \
10 20 30 70이를 배열로 표현하면 다음과 같다.
index 0 1 2 3 4 5 6
[100] [40] [80] [10] [20] [30] [70]그리고 배열의 인덱스만 가지고 부모와 자식의 위치를 계산할 수 있다.
C++처럼 배열의 인덱스를 0부터 사용한다고 가정하면 현재 노드의 인덱스가 i일 때
부모 노드
(i - 1) / 2
왼쪽 자식
2 * i + 1
오른쪽 자식
2 * i + 2가 된다.
예를 들어 index = 1인 40의 자식 노드를 찾아보자.
왼쪽 자식
2 * 1 + 1
= 3따라서
index 3
→ 10이고,
오른쪽 자식은
2 * 1 + 2
= 4이므로
index 4
→ 20이다.
실제 트리를 보면 정확히 일치한다.
40
/ \
10 20즉 완전 이진 트리라는 구조 덕분에 별도의 left, right 포인터 없이도 배열의 인덱스만 가지고 부모와 자식의 위치를 알아낼 수 있다.
이 특징 때문에 Heap을 배열이나 vector를 이용해 효율적으로 구현할 수 있다.
최대 힙(Max Heap)과 최소 힙(Min Heap)
이제 완전 이진 트리를 이해했다면 Heap의 두 가지 대표적인 형태를 알아보자.
Max Heap
Min Heap이다.
최대 힙(Max Heap)
최대 힙은 부모 노드의 값이 자식 노드의 값보다 크거나 같은 Heap이다.
부모 >= 자식예를 들어
100
/ \
40 80
/ \ / \
10 20 30 70을 보면
100 >= 40
100 >= 80
40 >= 10
40 >= 20
80 >= 30
80 >= 70이라는 조건을 모두 만족한다.
따라서 Root에는 항상 가장 큰 값이 위치한다.
Max Heap
Root
↓
가장 큰 값C++의 priority_queue는 기본적으로 최대 힙 형태로 동작한다.
최소 힙(Min Heap)
최소 힙은 반대로 부모 노드의 값이 자식 노드의 값보다 작거나 같은 Heap이다.
부모 <= 자식예를 들어
10
/ \
20 30
/ \ / \
40 50 60 70은 최소 힙 조건을 만족한다.
따라서 Root에는 항상 가장 작은 값이 위치한다.
Min Heap
Root
↓
가장 작은 값이 특징 덕분에 Heap을 이용하면 현재 데이터 중 가장 큰 값이나 가장 작은 값을 빠르게 확인할 수 있다.
Heap은 정렬된 자료구조일까?
여기서 내가 처음 잘못 이해했던 부분이 있다.
다음과 같이 데이터를 넣었다고 해보자.
priority_queue<int> pq;
pq.push(20);
pq.push(10);
pq.push(100);pop()을 반복하면
100
20
10순서로 나오기 때문에 처음에는
"priority_queue가 내부 데이터를 100, 20, 10 순서로 정렬해서 저장하는구나."
라고 생각했다.
하지만 그렇지 않다.
Heap이 보장하는 것은 부모와 자식 사이의 관계다.
최대 힙이라면
부모 >= 자식만 만족하면 된다.
예를 들어 다음 Heap을 보자.
100
/ \
40 80
/ \ / \
10 20 30 70배열로 표현하면
[100, 40, 80, 10, 20, 30, 70]이다.
이 배열은 전체적으로 내림차순 정렬되어 있지 않다.
40 < 80
30 < 70이기 때문이다.
하지만 Heap에서는 문제가 없다.
각 부모가 자신의 자식보다 크다는 조건을 만족하기 때문이다.
즉 Heap은
전체 데이터의 정렬을 보장하는 것이 아니라
가장 높은 우선순위의 데이터가
Root에 존재하는 것을 보장한다.
따라서 priority_queue 역시 모든 데이터를 정렬해서 저장하는 것이 아니라 우선순위가 가장 높은 데이터를 빠르게 꺼낼 수 있도록 Heap 구조를 유지하는 것이라고 이해하는 것이 정확하다.
새로운 데이터를 넣으면 Heap은 어떻게 유지될까?
그렇다면 새로운 데이터를 삽입했을 때 Heap 구조는 어떻게 유지되는 것일까?
최대 힙을 예로 들어보자.
현재 다음과 같은 Heap이 있다고 가정하자.
50
/ \
30 40여기에 100을 추가해보자.
완전 이진 트리의 구조를 유지해야 하기 때문에 새로운 데이터는 먼저 가장 마지막 위치에 들어간다.
50
/ \
30 40
/
100하지만 현재 상태에서는 최대 힙 조건을 만족하지 않는다.
30 < 100이기 때문이다.
따라서 부모와 위치를 교환한다.
50
/ \
100 40
/
30그런데 아직 끝이 아니다.
다시 부모와 비교한다.
100 > 50이므로 다시 교환한다.
100
/ \
50 40
/
30이제 최대 힙 조건을 만족한다.
이처럼 새로운 데이터를 마지막 위치에 추가한 뒤 부모와 비교하면서 위로 올라가는 과정을 Sift Up, 또는 Heapify Up이라고 한다.
새로운 데이터 삽입
↓
완전 이진 트리의 마지막 위치에 추가
↓
부모와 비교
↓
Heap 조건을 위반하면 교환
↓
다시 부모와 비교
↓
Heap 조건을 만족할 때까지 반복가장 높은 우선순위의 데이터를 제거하면?
이번에는 pop()을 생각해보자.
최대 힙에서는 Root에 가장 큰 값이 존재한다.
100
/ \
50 40
/ \
30 20여기서 100을 제거한다고 해보자.
Root를 그냥 제거하면 트리의 구조가 깨진다.
그래서 일반적으로 마지막 노드를 Root로 이동시킨다.
20
/ \
50 40
/
30하지만 현재 상태는 최대 힙 조건을 만족하지 않는다.
20 < 50따라서 자식들과 비교하면서 더 큰 자식과 위치를 교환한다.
50
/ \
20 40
/
30아직
20 < 30이므로 다시 교환한다.
50
/ \
30 40
/
20이제 Heap 조건을 만족한다.
이처럼 Root를 제거한 뒤 마지막 원소를 Root로 이동시키고, 자식과 비교하면서 아래로 내려가는 과정을 Sift Down, 또는 Heapify Down이라고 한다.
Root 제거
↓
마지막 원소를 Root로 이동
↓
자식과 비교
↓
Heap 조건을 위반하면 교환
↓
아래로 이동
↓
Heap 조건을 만족할 때까지 반복Heap의 시간복잡도
이제 왜 Heap을 사용하는지도 이해할 수 있다.
완전 이진 트리는 데이터의 개수가 N개일 때 트리의 높이가 대략
O(log N)이다.
Heap에 새로운 데이터를 추가하면 최악의 경우 Leaf에서 Root까지 올라가야 한다.
Leaf
↓
부모
↓
부모
↓
...
↓
Root따라서 push()의 시간복잡도는
O(log N)이다.
삭제 역시 Root에서 Leaf 방향으로 내려갈 수 있기 때문에
O(log N)이다.
반면 가장 높은 우선순위의 데이터는 항상 Root에 존재한다.
따라서 Root를 확인하기만 하면 되는 top()은
O(1)이다.
정리하면 다음과 같다.
| 연산 | 시간복잡도 |
|---|---|
top() | O(1) |
push() | O(log N) |
pop() | O(log N) |
여러 원소를 한꺼번에 Heap으로 구성하는 Heap Construction은 일반적으로 O(N)에 수행할 수 있다.
결국 Heap을 사용하는 중요한 이유는
가장 높은 우선순위의 데이터를 빠르게 확인하면서도 삽입과 삭제를 효율적으로 수행할 수 있기 때문
이라고 볼 수 있다.
C++의 priority_queue
이제 다시 C++로 돌아와보자.
C++ STL에서는 다음과 같이 우선순위 큐를 사용할 수 있다.
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(20);
pq.push(10);
pq.push(100);
cout << pq.top() << '\n';
pq.pop();
cout << pq.top() << '\n';
return 0;
}출력 결과는
100
20이다.
C++의 priority_queue는 기본적으로 가장 큰 값을 가장 높은 우선순위로 처리한다.
즉 기본적으로 최대 힙처럼 사용할 수 있다.
priority_queue의 템플릿 구조
이번에는 처음에 궁금했던 다음 코드를 다시 살펴보자.
priority_queue<int, vector<int>, greater<int>> pq;처음 보면
priority_queue인데 왜 vector가 들어가지?
greater<int>는 또 뭐지?라는 생각이 들 수 있다.
priority_queue의 템플릿 구조는 다음과 같다.
priority_queue<
저장할 자료형,
내부 컨테이너,
비교 기준
> pq;즉 세 가지를 지정할 수 있다.
무엇을 저장할 것인가?
어디에 저장할 것인가?
어떤 기준으로 우선순위를 정할 것인가?이를 코드에 그대로 대입하면
priority_queue<
int,
vector<int>,
greater<int>
> pq;는 다음과 같이 해석할 수 있다.
무엇을 저장할 것인가?
↓
int
어디에 저장할 것인가?
↓
vector<int>
어떤 기준으로 우선순위를 정할 것인가?
↓
greater<int>그런데 여기서 또 하나의 의문이 생긴다.
"priority_queue 자체가 자료구조 아닌가? 그런데 왜 데이터를 저장하기 위해 vector가 또 필요한 거지?"
이를 이해하려면 C++ STL의 Container와 Container Adaptor의 차이를 알아야 한다.
Container와 Container Adaptor
C++ STL에는 데이터를 관리하는 여러 자료구조가 존재한다.
대표적으로
vector
deque
list가 있다.
그리고
queue
stack
priority_queue도 존재한다.
겉으로 보면 모두 데이터를 저장하는 자료구조처럼 보이지만 C++ STL에서는 둘을 조금 다르게 구분한다.
핵심 기준은 다음과 같다.
Container
→ 데이터를 어떻게 저장할 것인가?
Container Adaptor
→ 저장된 데이터를 어떤 규칙으로 사용할 것인가?Container란?
Container는 실제로 여러 데이터를 저장하고 관리하는 객체다.
대표적으로
vector
deque
list등이 있다.
각각 데이터를 저장하는 방식에 차이가 있다.
| Container | 특징 |
|---|---|
vector | 연속된 메모리 공간에 데이터를 저장 |
deque | 앞과 뒤에서 삽입/삭제가 효율적 |
list | 각각의 노드를 연결해서 데이터를 저장 |
예를 들어 vector를 사용해보자.
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);개념적으로 다음과 같이 데이터가 실제로 저장된다.
vector<int>
┌────┬────┬────┐
│ 10 │ 20 │ 30 │
└────┴────┴────┘그리고 vector에서는 데이터에 비교적 자유롭게 접근할 수 있다.
v[0];
v[1];
v[2];
v.front();
v.back();즉 vector에서는 데이터가 어떻게 저장되는가라는 저장 구조 자체가 중요한 특징이다.
Container Adaptor란?
반면
queue
stack
priority_queue는 Container Adaptor에 해당한다.
Adaptor라는 이름처럼 기존 Container를 이용하되 데이터를 사용하는 방식을 특정 규칙에 맞게 제한해서 제공한다.
예를 들어 queue를 생각해보자.
queue<int> q;
q.push(10);
q.push(20);
q.push(30);Queue는 FIFO를 지켜야 하기 때문에 다음과 같은 접근은 제공하지 않는다.
q[1]; // 불가능대신 Queue에서 필요한 연산을 제공한다.
q.front();
q.back();
q.push();
q.pop();왜 그럴까?
Queue에서 중요한 것은
먼저 들어온 데이터를 먼저 꺼낸다.
라는 FIFO 규칙이기 때문이다.
개념적으로 생각하면 다음과 같다.
실제로 데이터가 저장된 공간
┌────┬────┬────┐
│ 10 │ 20 │ 30 │
└────┴────┴────┘
↓
queue가 사용하는 방법을 제한
꺼내기 ← 10 20 30 ← 넣기
FIFO즉 Container Adaptor는 새로운 저장 구조를 처음부터 만드는 것보다는 기존 Container를 사용하면서 특정 자료구조의 사용 규칙을 제공하는 역할을 한다.
Container와 Container Adaptor의 차이
전체적으로 보면 다음과 같다.
C++ STL
│
┌───────────┴───────────┐
│ │
Container Container Adaptor
"어떻게 저장?" "어떻게 사용할까?"
│ │
┌─────┼─────┐ ┌──────┼────────────┐
vector deque list queue stack priority_queue
│ │ │
FIFO LIFO 우선순위예를 들어 vector의 핵심은
연속된 메모리 공간에 데이터를 저장한다.
라는 저장 방식이다.
반면 queue의 핵심은
먼저 들어온 데이터를 먼저 사용한다.
라는 규칙이다.
stack은
가장 나중에 들어온 데이터를 먼저 사용한다.
라는 규칙을 가지고,
priority_queue는
가장 높은 우선순위의 데이터를 먼저 사용한다.
라는 규칙을 가진다.
한 문장으로 정리하면
Container는 데이터를 보관하는 구조가 핵심이고, Container Adaptor는 그 Container를 특정 규칙에 따라 사용하도록 인터페이스를 제한한 것이다.
라고 이해할 수 있다.
그래서 priority_queue에 vector가 들어간다
이제 처음 봤던 코드를 다시 보면 이해하기 쉬워진다.
priority_queue<
int,
vector<int>,
greater<int>
> pq;priority_queue는 데이터를 우선순위에 따라 사용하도록 만들어주는 Container Adaptor다.
따라서 실제 데이터를 저장할 Container가 필요하다.
여기서는
vector<int>가 그 역할을 담당한다.
개념적으로 보면 다음과 같다.
priority_queue
│
│ "우선순위에 따라 데이터를 관리할게."
│
▼
Heap 규칙 유지
│
▼
vector<int>
│
│ 실제 데이터 저장
▼
[ ... 실제 원소들 ... ]즉 priority_queue 안에 vector를 넣는다는 의미가 아니라,
priority_queue가 내부 저장 공간으로 vector를 사용한다.
라고 이해하는 것이 더 정확하다.
왜 기본적으로 vector를 사용할까?
C++의 priority_queue는 기본적으로 내부 Container로 vector를 사용한다.
따라서 다음 코드는
priority_queue<int> pq;실질적으로 기본 설정을 펼쳐 생각하면 다음과 같은 형태다.
priority_queue<
int,
vector<int>,
less<int>
> pq;Heap은 앞에서 살펴봤듯이 완전 이진 트리이기 때문에 배열 형태의 저장 구조와 잘 맞는다.
완전 이진 트리
↓
배열 인덱스로 부모/자식 위치 계산 가능
↓
연속적인 저장 구조 사용 가능
↓
vector와 잘 맞음그래서 vector를 이용해서 Heap을 효율적으로 관리할 수 있다.
최대 힙을 만들어보자
C++에서 다음과 같이 선언하면 기본적으로 가장 큰 값이 먼저 나온다.
priority_queue<int> pq;예를 들어
pq.push(20);
pq.push(10);
pq.push(100);
pq.push(50);을 넣으면
cout << pq.top();의 결과는
100이다.
이를 명시적으로 작성하면 다음과 같다.
priority_queue<
int,
vector<int>,
less<int>
> pq;즉 less<int>가 기본 비교 기준으로 사용된다.
최소 힙을 만들어보자
반대로 가장 작은 값을 먼저 꺼내고 싶다면 어떻게 해야 할까?
다음과 같이 작성할 수 있다.
priority_queue<
int,
vector<int>,
greater<int>
> pq;예를 들어
pq.push(20);
pq.push(10);
pq.push(100);
pq.push(50);을 넣으면
cout << pq.top();의 결과는
10이다.
따라서 pop()을 반복하면
10
20
50
100순서로 꺼낼 수 있다.
그런데 greater인데 왜 작은 값이 먼저 나오지?
이 부분 역시 처음 보면 꽤 헷갈린다.
greater<int>이라는 이름만 보면
"greater니까 큰 값이 먼저 나와야 하는 것 아닌가?"
라고 생각할 수 있다.
하지만 priority_queue에서 비교 함수는 단순히
어느 값을 앞으로 정렬할 것인가?라는 의미로만 해석하면 헷갈릴 수 있다.
실제로는 비교 기준을 이용해서 Heap Property를 구성하고, 비교 기준에서 우선순위가 낮다고 판단되는 원소가 아래쪽으로 배치된다고 생각하는 편이 낫다.
그래서 결과적으로
less<int>을 사용하면
큰 값이 top
→ Max Heap이 되고,
greater<int>을 사용하면
작은 값이 top
→ Min Heap이 된다.
처음에는 이름만 외우기보다 결과를 다음과 같이 기억하는 것이 편하다.
priority_queue<int>
priority_queue<int, vector<int>, less<int>>
→ 큰 값 먼저
→ Max Heappriority_queue<int, vector<int>, greater<int>>
→ 작은 값 먼저
→ Min Heap사용자 정의 자료형도 저장할 수 있을까?
지금까지는 int처럼 단순한 자료형만 저장했다.
하지만 실제 알고리즘 문제에서는 구조체나 클래스 객체의 우선순위를 직접 정의해야 하는 경우가 많다.
내가 최근 구현하고 있는 허프만 코딩(Huffman Coding)이 대표적인 예다.
허프만 알고리즘에서는 다음과 같은 노드를 사용할 수 있다.
struct Node {
char ch;
int freq;
Node* left;
Node* right;
};각 노드는 문자와 해당 문자의 등장 빈도 freq를 가지고 있다.
허프만 트리를 만들기 위해서는 매 순간 등장 빈도가 가장 작은 두 개의 노드를 꺼내야 한다.
예를 들어
A : 5
B : 10
C : 20
D : 30이 있다면
freq = 5
freq = 10인 두 노드를 먼저 가져와야 한다.
즉 최소 힙이 필요하다.
사용자 정의 Compare 만들기
하지만 다음과 같이 단순하게 작성할 수는 없다.
priority_queue<Node*> pq;Node*는 포인터이기 때문에 priority_queue가 우리가 원하는 freq 값을 기준으로 우선순위를 판단할 수 없다.
따라서 직접 비교 기준을 만들어줘야 한다.
struct Compare {
bool operator()(Node* a, Node* b) {
return a->freq > b->freq;
}
};그리고 다음과 같이 사용한다.
priority_queue<
Node*,
vector<Node*>,
Compare
> pq;이제 앞에서 배웠던 세 가지 질문을 그대로 적용해보자.
무엇을 저장할 것인가?
↓
Node*
어디에 저장할 것인가?
↓
vector<Node*>
어떤 기준으로 우선순위를 결정할 것인가?
↓
CompareCompare에서는
a->freq > b->freq를 사용하기 때문에 작은 freq를 가진 노드가 높은 우선순위를 가지게 된다.
따라서
freq = 5
freq = 10
freq = 20인 노드를 넣으면
pq.top();에서는
freq = 5인 노드를 얻을 수 있다.
허프만 알고리즘과 priority_queue
이제 허프만 알고리즘에서 왜 우선순위 큐를 사용하는지도 이해할 수 있다.
허프만 트리는 기본적으로 다음 과정을 반복한다.
등장 빈도가 가장 작은 노드 2개 선택
↓
두 노드를 하나의 부모 노드로 결합
↓
부모 노드의 빈도
= 두 자식 빈도의 합
↓
새로운 노드를 다시 후보에 삽입
↓
노드가 하나 남을 때까지 반복예를 들어
A : 5
B : 10
C : 20이라면 먼저
5
10을 꺼낸다.
그리고 새로운 노드를 만든다.
5 + 10 = 15다시 후보에 넣으면
15
20이 된다.
다시 두 노드를 꺼내
15 + 20 = 35를 만들면 최종 트리가 완성된다.
이 과정에서는 계속해서
현재 가장 작은 두 개의 값
을 빠르게 찾아야 한다.
매번 모든 데이터를 선형 탐색해서 최소값을 찾는 것보다 최소 힙 기반의 priority_queue를 사용하는 것이 효율적이다.
그래서 다음과 같은 코드가 자연스럽게 등장한다.
priority_queue<Node*, vector<Node*>, Compare> pq;결국 이 한 줄에는
허프만 노드의 주소를 저장하고
vector를 실제 저장 공간으로 사용하면서
freq가 작은 노드가 먼저 나오도록
Heap을 관리한다.라는 의미가 들어 있는 것이다.
처음에는 상당히 복잡해 보였던 코드지만 priority_queue의 구조를 하나씩 이해하고 나니 꽤 명확하게 읽힌다.
Queue와 Priority Queue의 차이 다시 보기
처음에 살펴봤던 Queue와 다시 비교해보자.
일반 Queue에서는
10
20
100순서로 넣었다면
10
↓
20
↓
100순서로 나온다.
중요한 것은 삽입 순서다.
반면 최대 힙 기반 Priority Queue에서는
10
20
100을 넣더라도
100
↓
20
↓
10순서로 나온다.
중요한 것은 우선순위다.
정리하면
Queue
→ 삽입된 순서를 기준으로 사용
→ FIFOPriority Queue
→ 설정된 우선순위를 기준으로 사용
→ Heap을 이용해 높은 우선순위의 원소를 빠르게 선택이라고 할 수 있다.
priority_queue는 언제 사용할까?
우선순위 큐는 단순히 코딩테스트에서만 사용하는 자료구조는 아니다.
여러 데이터 중에서 현재 가장 높은 또는 가장 낮은 우선순위의 데이터를 반복적으로 선택해야 하는 문제에서 사용할 수 있다.
대표적인 활용 사례를 살펴보자.
운영체제의 작업 스케줄링
운영체제에서는 여러 프로세스나 작업 중 어떤 작업을 먼저 처리할지를 결정해야 하는 상황이 존재한다.
만약 작업마다 우선순위가 존재한다면
작업 A : 우선순위 1
작업 B : 우선순위 10
작업 C : 우선순위 5Priority Queue를 사용해서 우선순위가 높은 작업을 빠르게 선택할 수 있다.
Priority Queue
↓
현재 가장 높은 우선순위 작업 선택다익스트라 알고리즘
다익스트라 알고리즘은 한 정점에서 다른 정점들까지의 최단 거리를 구하는 대표적인 최단 경로 알고리즘이다.
알고리즘을 수행하면서 계속
현재까지 발견된 거리 중 가장 짧은 정점은 무엇인가?
를 선택해야 한다.
단순 구현에서는 모든 정점을 탐색하면서 가장 가까운 정점을 찾을 수 있다.
이 경우 일반적으로
O(V²)의 시간복잡도를 가질 수 있다.
하지만 Min Heap 기반의 Priority Queue를 사용하면 가장 짧은 거리의 후보를 빠르게 선택할 수 있다.
일반적인 인접 리스트 기반 구현에서는 대략
O((V + E) log V)의 시간복잡도로 구현할 수 있고, 흔히 간단하게 O(E log V) 수준으로 표현하기도 한다.
여기서
V
→ 정점(Vertex)의 개수
E
→ 간선(Edge)의 개수다.
따라서 그래프의 크기가 커질수록 우선순위 큐의 장점이 크게 나타날 수 있다.
허프만 코딩
앞에서 살펴봤던 허프만 코딩 역시 대표적인 활용 사례다.
허프만 알고리즘에서는 계속
빈도가 가장 작은 노드 2개를 선택해야 한다.
따라서 Min Heap 기반의 Priority Queue가 매우 잘 맞는다.
가장 작은 두 노드 선택
↓
합치기
↓
다시 Priority Queue에 삽입
↓
반복Heap Sort
Heap 자체는 정렬 알고리즘에도 활용할 수 있다.
Heap Sort는 데이터를 Heap으로 만든 뒤 Root의 최댓값 또는 최솟값을 반복해서 제거하면서 정렬하는 방식이다.
예를 들어 Max Heap을 사용한다면 Root에는 항상 가장 큰 값이 있다.
Max Heap 생성
↓
Root의 최댓값 선택
↓
Heap에서 제거
↓
Heap 복구
↓
반복다만 Heap Sort는 priority_queue라는 C++ Container Adaptor의 활용이라기보다는 Heap 자료구조 자체를 이용한 정렬 알고리즘이라고 구분해서 이해하는 것이 좋다.
priority_queue를 언제 떠올리면 될까?
코딩테스트 문제를 풀다가 다음과 같은 표현이 등장한다면 Priority Queue를 한번 생각해볼 수 있다.
가장 큰 값을 반복해서 선택해야 한다.
가장 작은 값을 반복해서 선택해야 한다.
현재 가장 비용이 작은 후보를 선택해야 한다.
가장 우선순위가 높은 작업을 계속 처리해야 한다.
데이터가 계속 추가되는 상황에서
최댓값 또는 최솟값을 빠르게 찾아야 한다.특히 단순 정렬과 다른 점은 데이터가 계속 들어오고 나가는 상황이다.
처음부터 모든 데이터가 주어지고 한 번 정렬하면 끝나는 문제라면 sort()가 더 단순할 수 있다.
반면
데이터 삽입
↓
최솟값 꺼내기
↓
새로운 데이터 삽입
↓
다시 최솟값 꺼내기가 반복된다면 Priority Queue가 매우 유용하다.
정리
이번에는 C++의 priority_queue를 공부하면서 Queue부터 Heap, STL의 Container Adaptor까지 하나씩 연결해서 정리해보았다.
처음에는 우선순위 큐를 단순히
"큰 값이나 작은 값을 먼저 꺼내는 큐"
정도로만 알고 있었다.
하지만 내부 구조를 살펴보면 여러 개념이 연결되어 있었다.
Queue
↓
우선순위를 적용하고 싶다.
↓
Priority Queue
↓
가장 높은 우선순위의 데이터를
빠르게 찾을 방법이 필요하다.
↓
Heap
↓
Complete Binary Tree
↓
배열 / vector로 효율적으로 표현Heap은 완전 이진 트리를 기반으로 하며 최대 힙과 최소 힙으로 나눌 수 있다.
Max Heap
부모 >= 자식
Root = 가장 큰 값Min Heap
부모 <= 자식
Root = 가장 작은 값여기서 중요한 점은 Heap이 전체 데이터를 정렬해서 저장하는 자료구조가 아니라는 것이다.
Heap은 부모와 자식 사이의 관계를 유지함으로써 가장 높은 우선순위의 원소가 Root에 위치하도록 한다.
새로운 데이터가 들어오면
Sift Up을 통해 Heap Property를 복구하고,
Root가 제거되면
Sift Down을 통해 다시 Heap 구조를 유지한다.
이 덕분에 다음과 같은 성능을 얻을 수 있다.
| 연산 | 시간복잡도 |
|---|---|
top() | O(1) |
push() | O(log N) |
pop() | O(log N) |
그리고 C++의 priority_queue는 Container Adaptor다.
즉 자체적으로 데이터 저장 방식 자체를 정의하는 것보다는 내부 Container를 이용하면서 우선순위에 따른 사용 규칙을 제공한다.
따라서
priority_queue<
int,
vector<int>,
greater<int>
> pq;를 보면 이제 다음과 같이 해석할 수 있다.
무엇을 저장?
→ int
어디에 저장?
→ vector<int>
어떤 우선순위?
→ greater<int>
→ 작은 값 먼저사용자 정의 자료형도 같은 방식으로 해석할 수 있다.
priority_queue<Node*, vector<Node*>, Compare> pq;는
무엇을 저장?
→ Node*
어디에 저장?
→ vector<Node*>
어떤 우선순위?
→ Compare라는 의미다.
내가 허프만 알고리즘을 구현하면서 처음 이 코드를 봤을 때는
priority_queue<Node*, vector<Node*>, Compare> pq;한 줄에 왜 이렇게 많은 것이 들어가는지 이해하기 어려웠다.
하지만
Container
Container Adaptor
Heap
Compare의 관계를 하나씩 살펴보니 결국 각각 맡고 있는 역할이 명확하게 구분되어 있었다.
앞으로 코딩테스트에서 priority_queue가 등장한다면 단순히 코드를 외워서 사용하는 것이 아니라
"이 문제에서는 왜 우선순위 큐가 필요한가?"
"어떤 값을 가장 높은 우선순위로 두어야 하는가?"
"Max Heap이 필요한가, Min Heap이 필요한가?"
를 먼저 생각하면서 사용해봐야겠다.
