우선순위 큐, 힙과 이진 탐색 트리

이번 글에서는 우선순위 큐에 대해 알아봅니다. 이를 구현할 수 있는 두 가지 방법인 힙과 이진 탐색 트리에 대해서도 살펴봅니다.

목차

1. 우선순위 큐, 힙과 이진 탐색 트리

- 우선순위 큐란

- 힙이란

- 이진 탐색 트리란

2. 우선순위 큐의 구현

- 우선순위 큐의 두 가지 구현

- STL의 priority_queue와 multiset

3. 문제풀이: 힙과 이진 탐색 트리

- BOJ 11279번: 최대 힙 (실버 II)

- BOJ 1927번: 최소 힙 (실버 II)

- BOJ 11286번: 절대값 힙 (실버 I)

- BOJ 5639번: 이진 검색 트리 (골드 V)

4. 문제풀이: 우선순위 큐

- BOJ 7662번: 이중 우선순위 큐 (골드 IV)

- BOJ 2075번: N번째 큰 수 (실버 I)

- BOJ 11000번: 강의실 배정 (골드 V)

- BOJ 1715번: 카드 정렬하기 (골드 IV)

참고한 자료

C++ 자료구조론, Horowitz 외

http://www.yes24.com/Product/Goods/2656393

C++ 자료구조론 (2판) - YES24

알고리즘 문제 해결 전략, 구종만

https://book.algospot.com/

알고리즘 문제 해결 전략

알고리즘 트레이닝: 프로그래밍 대회 입문 가이드, 안티 라크소넨

http://www.yes24.com/Product/Goods/108202966

알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드 - YES24

---

우선순위 큐, 힙과 이진 탐색 트리

우선순위 큐란

우선순위 큐(priority queue)는 최대 또는 최소 원소를 탐색하거나 삭제할 수 있고, 임의의 원소를 삽입할 수 있는 자료구조입니다.

 

앞선 게시물에서 트리를 공부하면서 특정 조건을 지키도록 구성된 트리들은 탐색형 자료 구조로도 유용하게 쓰일 수 있다고 하였습니다. 우선순위 큐의 구현에는 특별한 형태의 이진 트리가 사용됩니다. 바로 힙과 이진 탐색 트리입니다.

힙이란

최대 힙(max heap)은 각 노드의 키 값이 자식 노드의 키 값보다 작지 않은 완전 이진 트리입니다. 최소 힙(min heap)도 이와 반대로 정의할 수 있습니다. 이 정의에 따라 최대 힙의 루트는 전체 트리에서 가장 큰 키 값을 가집니다. 또 힙은 완전 이진 트리이므로, 배열로 표현할 수 있습니다.

최대 힙에서의 삽입

최대 힙에서의 삽입 연산의 관건은 새 원소의 정확한 위치를 결정하는 것입니다. 이를 위해서는 완전 이진 트리에 노드 하나를 추가하고, 부모보다 자신이 클 경우 부모와 위치를 맞바꾸는 방식으로 올라가면 되겠죠.

최대 힙에서의 삭제

최대 힙에서의 삭제 연산의 경우 최대 원소(즉, 루트)를 삭제하게 됩니다. 그러면 비어버리는 루트를 무엇으로 채울까요? 완전 이진 트리의 마지막 원소를 삭제하고 거기 있던 값을 루트에 넣으면 될 것 같습니다. 그리고 자식보다 자신이 작을 경우 두 자식 중 더 큰 것과 맞바꾸는 것을 반복합니다.

이진 탐색 트리란

이진 탐색 트리(binary search tree)는 다음 성질을 만족시키는 이진 트리입니다.

1. 왼쪽 서브트리에 있는 키들은 그 루트의 키보다 작다.

2. 오른쪽 서브트리에 있는 키들은 그 루트의 키보다 크다.

3. 왼쪽, 오른쪽 서브트리도 모두 이진 탐색 트리이다.

순회와 탐색

이진 탐색 트리를 중위 순회하면 크기 순서로 정렬된 키의 목록을 얻을 수 있습니다. 또, 탐색은 이분 탐색과 비슷한 속도로 가능합니다.

삽입과 삭제

이진 탐색 트리에서의 삽입은 비교적 간단한데, 새 원소가 들어갈 위치를 이분 탐색과 유사한 방식으로 찾은 뒤 새 리프 노드로 추가하면 됩니다. 삭제의 경우, 리프 노드나 자식이 하나인 노드는 간단하고 자식이 둘인 노드도 어렵지 않습니다. 삭제하려는 원소를 왼쪽 서브트리에서 가장 큰 원소 또는 오른쪽 서브트리에서 가장 작은 원소로 대체하면, 대체한 원소는 원래 자식이 0 또는 1개임은 명백하므로 삭제 과정이 쉽습니다.

균형 잡힌 이진 탐색 트리

이진 탐색 트리가 만들어지는 방법(원소가 추가되는 순서)에 따라 노드가 한쪽으로 치우쳐 연결 리스트나 다름없게 되는 상황이 발생할 수 있습니다. 이 경우 연산이 그다지 효율적이지 못하게 되는데, 이를 방지하기 위해 여러 가지 '균형 잡힌 이진 탐색 트리(balanced binary search tree)'의 형태가 알려져 있습니다.

우선순위 큐의 구현

우선순위 큐의 두 가지 구현

우선순위 큐는 최대 또는 최소 원소를 쉽게 찾을 수 있도록 구현되어야 하므로, 힙이나 이진 탐색 트리를 이용하는 것이 효율적입니다. (균형 잡힌) 이진 탐색 트리는 최대 또는 최소 원소를 찾는 것이 \(O(\log n)\) 시간만큼 걸리는 반면 힙에서는 최대 또는 최소 원소가 반드시 루트에 있으므로 \(O(1)\)이죠. 따라서 힙이 우선순위 큐 구현에 더 적합한 것처럼 보입니다.

STL의 priority_queue와 multiset

우선순위 큐는 C++에서 priority_queue라는 구현체가 있습니다. 내부적으로는 힙을 이용하며 최대 또는 최소 원소를 빠르게 구할 수 있습니다.

priority_queue<int> q; // max heap 기반
priority_queue<int, vector<int>, greater<int>> q2; // min heap 기반

한편 multiset은 같은 값을 여러 개 가질 수 있는 집합 자료구조인데, 균형 잡힌 이진 탐색 트리를 기반으로 만들어져 있으며 우선순위 큐의 연산을 모두 지원하기 때문에 우선순위 큐처럼 쓸 수 있습니다. 하지만 실험에 의하면 속도가 다섯 배 정도 느립니다.

문제풀이: 힙과 이진 탐색 트리

BOJ 11279번: 최대 힙 (실버 II)

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

최대 힙을 만들어보는 문제입니다. 물론 STL의 자료구조를 컨테이너를 사용해도 될 듯하지만 연습삼아 구현해 보았습니다.

#include <iostream>
#include <vector>
using namespace std;

#define ll long long

void I(vector<ll>& maxheap, ll x) {
	maxheap.push_back(x); // insert at end position
	int idx = maxheap.size() - 1;
	while (idx > 0 && maxheap[(idx - 1) / 2] < maxheap[idx]) {
		// if parent is smaller, swap and move to the parent
		swap(maxheap[idx], maxheap[(idx - 1) / 2]);
		idx = (idx - 1) / 2;
	}
}

void D(vector<ll>& maxheap) {
	if (maxheap.empty()) {
		cout << "0\n";
		return;
	}
	cout << maxheap.front() << "\n"; // print max value
	maxheap[0] = maxheap.back();
	maxheap.pop_back();
	int idx = 0;
	int child = idx * 2 + 1;
	while (child < maxheap.size()) {
		// child = current node's bigger child
		if (child + 1 < maxheap.size() && maxheap[child] < maxheap[child + 1]) child++;
		if (maxheap[idx] >= maxheap[child]) break; // if current node is bigger than children, there is no need to move down
		swap(maxheap[idx], maxheap[child]);
		idx = child;
		child = child * 2 + 1;
	}
}

int main() {
	// using cin & cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input
	int N;
	cin >> N;

	// operation
	vector<ll> maxheap;
	for (int i = 0; i < N; i++) {
		ll x;
		cin >> x;
		if (x > 0) I(maxheap, x);
		else D(maxheap);
	}

	return 0;
}

BOJ 1927번: 최소 힙 (실버 II)

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

이번엔 최소 힙의 구현입니다.

#include <iostream>
#include <vector>
using namespace std;

#define ll long long

void I(vector<ll>& minheap, ll x) {
	minheap.push_back(x); // insert at end position
	int idx = minheap.size() - 1;
	while (idx > 0 && minheap[(idx - 1) / 2] > minheap[idx]) {
		// if parent is bigger, swap and move to the parent
		swap(minheap[idx], minheap[(idx - 1) / 2]);
		idx = (idx - 1) / 2;
	}
}

void D(vector<ll>& minheap) {
	if (minheap.empty()) {
		cout << "0\n";
		return;
	}
	cout << minheap.front() << "\n"; // print min value
	minheap[0] = minheap.back();
	minheap.pop_back();
	int idx = 0;
	int child = idx * 2 + 1;
	while (child < minheap.size()) {
		// child = current node's smaller child
		if (child + 1 < minheap.size() && minheap[child] > minheap[child + 1]) child++;
		if (minheap[idx] <= minheap[child]) break; // if current node is smaller than children, there is no need to move down
		swap(minheap[idx], minheap[child]);
		idx = child;
		child = child * 2 + 1;
	}
}

int main() {
	// using cin & cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input
	int N;
	cin >> N;

	// operation
	vector<ll> minheap;
	for (int i = 0; i < N; i++) {
		ll x;
		cin >> x;
		if (x > 0) I(minheap, x);
		else D(minheap);
	}

	return 0;
}

BOJ 11286번: 절댓값 힙 (실버 I)

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

절댓값이 가장 작은 원소가 루트에 있도록 하는데, 절댓값이 같은 경우 원소 값이 작아야 함에 유의합니다.

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

#define ll long long

bool compare(ll x, ll y) {
	if (llabs(x) != llabs(y)) return llabs(x) > llabs(y);
	return x > y;
}

void I(vector<ll>& heap, ll x) {
	heap.push_back(x); // insert at end position
	int idx = heap.size() - 1;
	while (idx > 0 && compare(heap[(idx - 1) / 2], heap[idx])) {
		// if parent's absolute value is bigger, swap and move to the parent
		swap(heap[idx], heap[(idx - 1) / 2]);
		idx = (idx - 1) / 2;
	}
}

void D(vector<ll>& heap) {
	if (heap.empty()) {
		cout << "0\n";
		return;
	}
	cout << heap.front() << "\n"; // print min value
	heap[0] = heap.back();
	heap.pop_back();
	int idx = 0;
	int child = idx * 2 + 1;
	while (child < heap.size()) {
		// child = current node's smaller child
		if (child + 1 < heap.size() && compare(heap[child], heap[child + 1])) child++;
		if (!compare(heap[idx], heap[child])) break; // if current node is smaller than children, there is no need to move down
		swap(heap[idx], heap[child]);
		idx = child;
		child = child * 2 + 1;
	}
}

int main() {
	// using cin & cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input
	int N;
	cin >> N;

	// operation
	vector<ll> heap;
	for (int i = 0; i < N; i++) {
		ll x;
		cin >> x;
		if (x != 0) I(heap, x);
		else D(heap);
	}

	return 0;
}

유의사항을 고려해 비교 함수를 따로 구현해 주었습니다.

BOJ 5639번: 이진 검색 트리 (골드 V)

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

이진 검색 트리라는 조건이 있기에, 전위 순회만 알려 줬지만 중위 순회도 아는 것이나 다름없습니다.

#include <cstdio>
#include <algorithm>
using namespace std;

int preorder[10000];

void postorder(int left, int right) {
	if (left >= right) return;
	int* inorder = new int[right - left];
	for (int i = 0; i < right - left; i++) {
		inorder[i] = preorder[left + i];
	}
	sort(inorder, inorder + right - left);
	const int root = preorder[left];
	int idx = find(inorder, inorder + right - left, root) - inorder;
	postorder(left + 1, left + 1 + idx);
	postorder(left + 1 + idx, right);
	printf("%d\n", root);
}

int main() {
	// input
	int node;
	int i = 0;
	while (scanf("%d", &node) == 1) {
		preorder[i++] = node;
	}

	// output
	postorder(0, i);

	return 0;
}

 

문제풀이: 우선순위 큐

BOJ 7662번: 이중 우선순위 큐 (골드 IV)

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

우선순위 큐를 구현하는데, 최대값과 최소값을 모두 관리할 수 있어야 합니다.

#include <iostream>
#include <set>
using namespace std;

int main() {
	// using faster cin & cout
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// input
	int T;
	cin >> T;
	for (int t = 0; t < T; t++) {
		int k;
		cin >> k;
		multiset<int> Q;
		for (int i = 0; i < k; i++) {
			char op;
			int n;
			cin >> op >> n;
			if (op == 'I') {
				Q.insert(n);
			}
			else if (op == 'D') {
				if (Q.empty()) continue;
				else if (n == 1) Q.erase(--Q.end());
				else if (n == -1) Q.erase(Q.begin());
			}
		}
		if (Q.empty()) cout << "EMPTY\n";
		else cout << *Q.rbegin() << " " << *Q.begin() << "\n";
	}

	return 0;
}

multiset을 쓰면 나름대로 쉽게 해결할 수 있습니다. 하지만, 직접 구현한다면 어려울 수 있는 문제였어요.

BOJ 2075번: N번째 큰 수 (실버 I)

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

#include <iostream>
#include <queue>
using namespace std;

#define ll long long

int main() {
	// using faster cin & cout
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// input line 1
	int N;
	cin >> N;

	// using priority queue
	priority_queue<int, vector<int>, greater<int>> q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ll num;
			cin >> num;
			q.push(num);
		}
		while (q.size() > N) {
			q.pop();
		}
	}
	
	cout << q.top();

	return 0;
}

우선순위 큐를 사용하는데, 메모리 제한이 타이트해서 큐의 사이즈를 주기적으로 줄여주었습니다.

BOJ 11000번: 강의실 배정 (골드 V)

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

#include <iostream>
#include <queue>
using namespace std;

#define ll long long

struct meeting {
	ll begin;
	ll end;
};

bool operator>(meeting left, meeting right) {
	if (left.begin != right.begin) return left.begin > right.begin;
	return left.end > right.end;
}

int main() {
	// using faster cin & cout
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// input line 1
	int N;
	cin >> N;

	// input line 2 ~ N + 1
	priority_queue<meeting, vector<meeting>, greater<meeting>> q; // sort by begin time, then end time (ascending)
	for (int i = 0; i < N; i++) {
		meeting m;
		cin >> m.begin >> m.end;	
		q.push(m);
	}

	// room scheduling
	priority_queue<ll, vector<ll>, greater<ll>> room;
	while (!q.empty()) {
		if (!room.empty() && room.top() <= q.top().begin) {
			// the first ending class ends before new class begins
			room.pop(); // we can use existing room
		}
		room.push(q.top().end); // update new class end time
		q.pop();
	}

	// output
	cout << room.size();

	return 0;
}

꽤 생각을 잘 해야 하는 문제로, 우선 수업들을 먼저 시작하는 순서대로 (똑같이 시작하면, 먼저 끝나는 순서대로) 정렬해 둬야 합니다. 그 뒤 room이라는 이름의 우선순위 큐에 각 수업이 끝나는 시간을 집어넣는데, 만약 수업이 시작하는 시간보다 '가장 먼저 끝나는 수업의 끝나는 시간'이 더 이르다면 그 강의실에 수업을 집어넣으면 되니, '가장 먼저 끝나는 수업'을 우선순위 큐에서 제거하고 이 수업이 끝나는 시간을 새로 집어넣습니다.

BOJ 1715번: 카드 정렬하기 (골드 IV)

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

#include <iostream>
#include <queue>
using namespace std;

int main() {
	// using faster cin & cout
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// input line 1
	int N;
	cin >> N;

	// input line 2 ~ N + 1
	priority_queue<int, vector<int>, greater<int>> q;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		q.push(num);
	}

	// operation
	int ops = 0;
	while (q.size() > 1) {
		int a = q.top();
		q.pop();
		int b = q.top();
		q.pop();
		q.push(a + b);
		ops += a + b;
	}

	// output
	cout << ops;

	return 0;
}

카드의 묶음을 우선순위 큐에 넣고 가장 적은 것 두 개를 계속 뽑아서 더하고 더한 묶음을 넣는 것을 반복하면 됩니다.

---

즐겁다! 다음 주제는 그래프 탐색입니다. (DFS와 BFS)