알고리즘 - 힙 & 우선순위 큐

이번 시간에는 힙&우선순위 큐에 대해서 알아보도록 하겠습니다.

 

 힙은 완전 이진 트리의 일종입니다. 힙은 우선순위 큐를 위해 만들어진 자료구조이며 정렬하기에 따라 Min 힙과 Max 힙으로 나뉘어집니다.

 

 완전 이진 트리의 일종이므로 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있으며, 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워나가게 됩니다.

 

그렇기 때문에 해당 특징을 가지게 됩니다.

1. [부모 노드]가 가진 값은 항상 [자식 노드]가 가진 값보다 크다.

2. 노드 개수를 알면, 트리 구조는 무조건 확정할 수 있다.

 

완전 이진트리이기 때문에 각각의 노드들은 연결되어 저장되게 된다. (배열의 형태)

힙에 대한 구현은 뒤에서 우선순위 큐를 구현하며 같이 보도록 하겠습니다.

 

 우선순위 큐는 힙 자료구조에 큐의 특징을 더한 자료구조입니다. 위에서 언급한 것처럼 배열의 형태로 저장이 가능하기 때문에 맨 앞과 뒤가 주어지게 됩니다. 여기에 큐에서 제공하는 선입선출의 기능을 더해 힙에서 가장 앞의 원소를 반환하고, 맨 뒤에 새로운 원소를 추가할 수 있는 구조가 바로 우선순위 큐입니다.

 

 힙 자료구조에 큐의 기능을 만들기 위해서는 무엇보다 push와 pop의 기능이 있어야 할 것입니다. 그렇다면 하나씩 기능을 어떻게 구현할지에 대해서 알아보도록 하겠습니다. 

 

 우선  push의 경우 힙을 저장하고 있는 배열의 끝에 새로운 원소를 추가하는 기능입니다. 단순히 추가만 한다면 간단하겠지만, 우선순위 큐는 위에서 작성한 특징(1)에 의하여 부모/자식 노드간 일정한 규칙에 의해 정렬이 되어야 합니다. 그렇기 때문에 아래서부터 부모 노드와 비교하며 부모노드보다 작을때까지 부모 노드와 스왑을 진행하며 올라가게 되고, 최종적으로 정렬된 우선순위 큐의 형태를 띄게 될 것입니다.

 

 다음으로 pop의 경우 맨 앞에 있는 값을 빼야 하는데 배열에서 단순하게 이 과정을 거칠 경우에 불필요한 계산이 발생하므로 마지막 인덱스의 값과 먼저 스왑하여 위치를 바꾸고, 맨 마지막 인덱스를 지우는 과정을 거칩니다. 그렇게 하게되면 의도대로 맨 앞에 있던 값은 지워지게 되지만 기존에 마지막에 있던 원소가 맨 앞에 있게 됩니다. 그렇기 때문에 기존에 있던 위치로 옮기기 위해 push와는 반대로 자식노드와 값을 비교하며 아래로 내려가게 됩니다. 이 과정 중, 최대 두 개의 자식노드를 가지므로 정렬에 대한 계산을 최소화하기 위해서 자식 노드중에서 큰 노드와 값을 비교하여 재귀적으로 정렬을 반복하게 되면 우선순위 큐가 다시 규칙에 맞게 정렬되게 됩니다.

 

그렇다면 코드를 통해 우선순위 큐에 대해서 살펴보도록 하겠습니다.

template<typename T, typename Container = vector<int>, typename Predicate = less<T>>
class PriorityQueue
{
public:
	void push(const T& data)
	{
		// 우선 힙 구조부터 맞춰준다.
		_heap.push_back(data);

		// 도장깨기 시작
		int now = static_cast<int>(_heap.size()) - 1;

		// 루트 노드까지
		while (now > 0)
		{
			// 부모 노드의 데이터와 비교해서 더 작으면 패배
			int next = (now - 1) / 2;
			if (_predicate(_heap[now], _heap[next]))
				break;

			// 데이터 교체
			::swap(_heap[now], _heap[next]);
			now = next;
		}
	}

	void pop()
	{
		_heap[0] = _heap.back();
		_heap.pop_back();

		int now = 0;

		while (true)
		{
			// now 노드의 좌우 자식노드
			int left = now * 2 + 1;
			int right = now * 2 + 2;

			// 리프에 도달한 경우
			if (left >= _heap.size())
				break;

			int next = now;

			// 왼쪽과 비교
			if (_predicate(_heap[next], _heap[left]))
				next = left;

			// 둘 중 승자를 오른쪽과 비교
			if (right < _heap.size() && _predicate(_heap[next], _heap[right]))
				next = right;

			// 왼쪽/오른쪽 둘 다 현재 값보다 작으면 종료
			if (next == now)
				break;

			::swap(_heap[now], _heap[next]);

			now = next;
		}

	}

	bool empty()
	{
		return _heap.size() == 0;
	}

	T& top()
	{
		return _heap[0];
	}

private:
	Container _heap = {  };
	Predicate _predicate = {};
};

그렇다면 이상으로 힙&우선순위 큐에대한 설명을 마치겠습니다. 포바~!