[자료구조] 힙과 우선순위 큐(Heap and Priority Queue)

힙과 우선순위 큐

 

1. 우선순위 큐

 

Priority Queue(우선순위 큐)는 우선순위를 가진 원소들을 저장하고 우선순위가 높을수록 먼저 출력하는 자료구조이다.

 

우선순위 큐의 ADT를 살펴봤을 때 핵심적인 기능으로는 '삽입, (우선순위 제일 높은 원소) 삭제, (우선순위 제일 높은 원소) 반환'이 있다.

우선순위 큐는 여러가지 방법으로 구현이 가능하다.

 

1) 비정렬 시퀀스를 이용한 구현

 

우선순위 큐를 비정렬 시퀀스를 이용해 구현하는 경우 삽입은 간단하다.

비정렬 시퀀스이므로 시퀀스의 마지막에 삽입하고자 하는 원소를 담은 노드를 매달아 주면 된다.

O(1)의 시간이 걸릴 뿐이다.

n개의 모든 원소 삽입에 대해 O(1)이 시간이 걸리므로 총 O(n)의 시간이 걸린다.

 

하지만 우선순위 제일 높은 원소를 찾아 반환하거나 삭제하고자 할 때는 그리 간단하지 않다.

비정렬 시퀀스이기 때문에 우선순위가 제일 높은 원소를 찾을 때 최악의 경우 모든 원소를 탐색해야 할 수 있다.

따라서 한번의 반환 함수 또는 삭제 함수를 수행할 때 O(n)의 시간이 걸리게 된다.

즉, n개의 원소에 대해 O($n^2$)의 시간이 걸린다.

 

2) 정렬 시퀀스를 이용한 구현

 

우선순위 큐의 구현에 정렬 시퀀스를 이용하게 되면 우선순위 큐에 원소를 삽입하는 족족 내부에서 정렬이 되어야 한다.

시퀀스에서 하나의 원소를 우선순위에 맞추어 정렬하는 데 O(n)의 시간이 걸리므로,

n개의 원소 삽입 시 O($n^2$)의 시간이 걸린다.

 

반면 원소들이 정렬 시퀀스에 우선순위 순으로 정렬되어 저장되어 있으므로

우선순위 제일 높은 원소를 찾아 반환하거나 삭제하고자 할 때 시퀀스 맨 앞의 원소를 바로 반환하거나 삭제하면 된다.

따라서 O(1)의 시간이 걸리고 n개의 원소에 대해서는 O(n)의 시간이 걸리게 된다.

 

 

2. 힙

 

heap(힙)은 우선순위 큐 구현에 쓰이는 대표적인 자료구조로 키들을 내부 노드들에 저장하는 이진 트리이다.

힙은 이에 추가로 힙 순서 특성과 완전 이진 트리 특성이라는 두 가지 특성을 만족해야 한다.

 

힙 순서 특성이란 트리의 루트를 제외한 모든 노드 v에 대해, v에 저장된 키의 우선순위는 부모에 저장된 키의 우선순위보다 작거나 같아야 한다는 것을 의미한다.

 

완전 이진 트리 특성(Complete Binary Tree)이란 트리의 마지막 레벨을 제외한 모든 레벨이 가질 수 있는 최대 수의 노드를 포함하고, 마지막 레벨의 경우 제일 왼쪽부터 차례대로 채워지는 트리의 특성을 의미한다.

 

힙이 완전 이진 트리 구조를 가지는 것은 앞으로의 구현과 성능에 있어 큰 의미를 지닌다.

이때, complete binary tree와 헷갈리기 쉬운 proper binary tree의 개념을 짚고 넘어가고자 한다.

proper binary tree란 모든 노드의 자식 노드 개수가 0개 또는 2개인 이진 트리를 말한다.

아래 그림은 둘의 차이가 잘 드러난다.

 

 

x 노드의 자식 노드가 1개이므로 Proper Binary Tree에 해당하지 않는다.

 

이진 트리의 경우 특정한 규칙에 의해 각 노드의 번호를 매길 수 있다.

root 노드의 경우 1번,

임의의 노드 번호가 x번일 경우, 해당 노드의 왼쪽 자식은 2*x번, 오른쪽 자식은 2*x + 1번에 해당한다.

완전 이진 트리의 경우 n개의 노드에 대해 1번부터 n번까지 모든 노드가 차례로 존재함을 알 수 있다.

따라서 배열로 트리를 구현하여도 메모리의 낭비 없이 매우 효과적인 사용이 가능하다.

단, 노드의 번호는 1부터 시작하는데 반해 이에 대응하는 배열의 인덱스는 0부터 시작하므로 배열의 첫 번째 원소는 의미 없는 값으로 채워 넣는다.

 

이제 구체적인 예를 통해 힙의 구현 과정을 살펴보자.

예시를 통해 살펴 볼 힙은 원소의 값이 작을수록 우선순위가 높은 min-heap이다.

 

1) 삽입

 

힙에 새로운 노드를 삽입 시 완전 이진 트리의 구조적 조건을 유지하기 위해 다음을 따른다.

 

- 만약 바닥 레벨이 꽉 차지 않았으면, 바닥 레벨의 가장 오른쪽에 있는 노드의 바로 다음에 새 노드 삽입

- 만약 바닥 레벨이 꽉 찼다면, 바닥 레벨의 가장 왼쪽에 있는 노드의 왼쪽 자식으로 새 노드 삽입

 

이제 힙의 순서 특징을 만족시키기 위한 up-heap bubbling(업-힙 버블링)이 일어난다.

예시의 힙은 min-heap이므로 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 한다.

새로 추가된 노드가 이를 위반할 시 부모 노드와 저장된 원소를 교환하면 된다.

이 교환으로 인해 새로운 노드가 한 레벨 상승하게 되므로 up-heap이라 부른다.

이 과정은 새로운 노드가 min-heap의 순서 특징을 만족할 때까지 반복된다.

 

다음 그림과 같은 힙에 원소값을 5로 갖는 노드를 삽입하는 과정을 살펴보자.

 

 

앞의 설명에 따라 5를 삽입한 순간 힙은 완전 이진 트리의 구조를 만족시키기 위해 아래 그림과 같다.

 

 

5의 부모 노드의 원소 값 50은 힙의 순서 특성을 위배한다.

따라서 두 노드의 원소값 교환이 일어난 후의 힙은 아래 그림과 같다.

 

 

한 레벨 올라간 후 5의 부모 노드의 원소값 10 또한 힙의 순서 특성을 위배하므로 교환이 진행된다.

 

 

 

더 이상 비교할 부모 노드가 없으므로 삽입 과정이 끝났다.

5를 삽입한 후 최종적인 힙은 위의 사진과 같다.

 

2) 삭제

 

삭제 후에도 힙은 구조적 특성과 순서 특성을 만족해야 한다.

삭제를 할 경우 우선순위가 제일 높은 원소가 저장된 root 노드가 삭제되어야 한다.

이때 물리적으로 root 노드를 삭제해버리면 완전 이진 트리의 구조가 망가져 버린다.

이를 다시 보수하기는 상당히 번거롭다.

 

따라서 힙의 마지막 노드와 루트 노드의 값을 교환한 후 마지막 노드(원래의 루트 값)를 삭제한다.

이는 원래 삭제하고자 했던 루트 값을 삭제함과 동시에 완전 이진 트리 구조 또한 망가뜨리지 않는다.

하지만 마지막 노드에 있던 원소 값이 루트 노드에 저장된 상태이므로 힙의 순서 특성을 위배할 가능성이 매우 높다.

이를 다시 보수하기 위해 down-heap bubbling이 진행된다.

이번에는 루트 노드부터 시작해 부모 노드와 자식 노드와 값을 비교해 힙의 순서 특성을 만족할 때까지 교환하며 내려간다.

이때 부모 노드가 왼쪽 자식과 오른쪽 자식 둘 다 갖는 경우 왼쪽 자식과 오른쪽 자식 중 우선순위가 더 높은 자식과 교환한다.

 

위의 힙에서 삭제 과정이 일어나는 과정을 살펴보자.

 

 

원래 마지막 노드의 원소 값이었던 50이 root 노드에 저장된 상태이다.

자식 노드들의 값(20, 10) 보다 크므로 min-heap의 순서 특성에 위배된다.

오른쪽 자식의 원소 값이 더 작으므로 루트 노드와 오른쪽 자식 노드와의 교환이 일어난다.

 

 

이로써 삭제가 완료된다.

 

앞서 시퀀스를 이용해 우선순위 큐를 구현하는 방법에 대해 알아보았다.

n개의 원소를 삽입 및 삭제하는 과정에서 O($n^2$)의 시간이 걸리는 것을 확인하였다.

반면 우선순위 큐 구현에 힙을 사용하면 O(nlogn)의 시간이 걸린다.

이는 힙이 완전 이진 트리의 구조를 가짐에 따라 그 높이에 의해 증명 가능하다.

그 증명 과정은 생략하도록 한다.

 

/*
20191111
Data Structure Min-Heap Inplementation
*/
#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Heap {
public:
	vector<int>heap;
	int n;

	Heap() {
		heap.push_back(-1);
		n = 0;
	}

	void swapHeap(int* a, int* b) {
		int tmp = *a;
		*a = *b;
		*b = tmp;
	}

	void insert(int value) {
		heap.push_back(value);
		n++;
		int child = n;
		int parent = child / 2;

		while (child > 1 && heap[child] < heap[parent]) {
			swapHeap(&heap[child], &heap[parent]);
			child = parent;
			parent = child / 2;
		}
	}

	int size() {
		return n;
	}

	int pop() {
		if (n < 1) {
			return -1;
		}

		else {
			int res = heap[1];
			swapHeap(&heap[1], &heap[n--]);
			heap.pop_back();
			int parent = 1;
			int child = parent * 2;

			if (child + 1 <= n)
				child = (heap[child + 1] >= heap[child] ? child : child + 1);

			while (child <= n && heap[child] < heap[parent]) {
				swapHeap(&heap[child], &heap[parent]);
				parent = child;
				child = parent * 2;

				if (child + 1 <= n)
					child = (heap[child + 1] >= heap[child] ? child : child + 1);
			}

			return res;
		}
	}

	int top() {
		if (n < 1)
			return -1;
		else
			return heap[1];
	}

	int isEmpty() {
		if (n < 1)
			return 1;
		else
			return 0;
	}

	void print() {
		if (n >= 1) {
			for (int i = 1; i <= n; i++)
				cout << heap[i] << " ";
			cout << "\n";
		}
		else
			cout << "-1\n";
	}
};

int main() {
	int N, input;
	string cmds;
	Heap hp;

	cin >> N;

	while (N--) {
		cin >> cmds;
		if (cmds == "insert") {
			cin >> input;
			hp.insert(input);
		}
		else if (cmds == "size")
			cout << hp.size() << "\n";
		else if (cmds == "isEmpty")
			cout << hp.isEmpty() << "\n";
		else if (cmds == "pop")
			cout << hp.pop() << "\n";
		else if (cmds == "top")
			cout << hp.top() << "\n";
		else
			hp.print();
	}
}