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

🔻이진 트리(Binary Tree)

 먼저 힙에 대해 알아보기전에 이진트리에 대해서 간단히 알아보도록 하겠다. 왜냐하면 힙이 이진 트리로 구현되는 자료구조이기 때문이다.

 이진 트리란 한 노드가 최대 두개의 노드를 자식으로 가질 수 있는 트리이다. 그 중에서도, 마지막 레벨을 제외한 모든 레벨에는 노드들이 가득차있고, 마지막 레벨의 노드들도 좌측부터 순서로 들어가있는 형태의 이진 트리를 완전 이진 트리 라고한다.

 이 완전이진트리는 이러한 구조적 특징때문에 노드의 개수를 알면 트리의 구조를 특정할 수 있다는 성질이 있다. 또 이러한 성질 때문에 아래와 같은 성질을 가지고 있다.

 

현재 노드 번호를 i라 할때, 
 ◾ 현재 노드의 perent node의 번호 = (i - 1) / 2
 ◾ 현재 노드의 left child node의 번호 = i * 2 + 1
 ◾ 현재 노드의 right child node의 번호 = i * 2 + 2
    (Root node가 0번일 경우 기준)

 

 위와 같은 성질을 가지고 있다. 이러한 성질이 있기에 1차원 배열로 이진 트리를 나타내기 용이하다. 현재 이진트리에 대한 글이 아니니 이정도만 알아보고 힙으로 넘어가보도록하자.

 

 

🔻힙(Heap)

 힙은 위에서 설명한 완전 이진 트리로 구현된 자료구조이다. 영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻을 지니고 있다. 부모 노드가 가진 값은 자식 노드의 값보다 무조건 크거나(Max Heap) 작아야(Min Heap) 한다. 또한 완전 이진 트리이므로 위에서 설명한 구조적 특징으로 배열을 통해 구현가능 하다.

 부모 노드의 값이 무조건 자식 노드의 값보다 큰 힙을 Max Heap, 작은 힙을 Min Heap이라고 하는데, 설명의 편의를 위해 MaxHeap을 기준으로 설명해보도록 하겠다.

 위의 그림이 MaxHeap의 모습이다. 보면 알겠지만 들어가있는 데이터중 Root의 값이 가장 크다. 또한 모든 서브트리에 대해서도 같다. 이러한 성질을 이용해서, 가장 크거나 작은 값을 찾아내는 연산을 빠르게 하기위해 고안된 자료구조라고 할 수 있다. 가장 큰 값을 구하고자 할때 Root의 값을 가져오면 되므로 O(1)의 시간복잡도를 가진다.

 

 

 

🔶자료의 추가

그러면 이 힙에 자료를 추가하려면 어떻게 해야할까?

 

   1. 새로운 노드를 트리의 맨 뒤에 추가한다. (완전 이진 트리의 형태를 깨면 안됨)
   2. 추가된 노드와 부모 노드를 비교하여 자식 노드가 크다면 서로의 위치를 바꾼다.
   3. 2번 작업을 부모 노드가 더 클때까지 반복한다.

 

이러한 작업을 통해여 자료를 추가할 수 있다. 글로만 보면 이해하기 힘들 수 있으니 그림을 통해 알아보자.

 MaxHeap에 50의 값을 가진 노드를 추가하려는 상황이다. 그러면 이 노드는 트리의 맨 뒤인 13의 rightChild로 들어가게 된다.

 

 50의 부모노드인 13과 비교한다. 50이 크므로 둘의 자리를 바꿔준다.

자리를 바꾸고 또 바꾼 자리의 부모노드인 44와 비교한다. 또 50이 크므로 자리를 바꿔준다.

올라오다 보니 root 바로아래까지 왔다. 부모 노드인 55와 비교하지만 55가 크므로 자리를 고정하고 자료의 추가가 완료된다. 이렇게 되면 Heap의 특징인 부모 노드가 가진 값은 자식 노드의 값보다 무조건 크거나(Max Heap) 작아야(Min Heap) 한다. 라는 조건이 만족된다.

 

💡시간복잡도

 그러면 자료를 추가하는 작업의 시간복잡도를 계산해보자. 일단 최악의 상황인 추가된 노드가 부모 노드와 비교를 하다가 Root노드와 비교하는 상황까지 가는 것이 최악의 상황일 것이다. 이때는 트리의 높이만큼의 비교를 한다고 생각할 수 있다. 트리의 높이는 마지막 레벨까지 꽉찬 포화 이진 트리에서 log(n+1)로 나타낼 수 있고 꽉차지 않더라도 이에 근사하므로 자료를 추가하는 시간복잡도는 O(logN)이다.

 

 

🔶자료의 삭제

 다음으로는 자료의 삭제이다. 자료가 삭제되는 경우는 맨 위에있는 Root노드가 빠지는 경우밖에 없다. 그렇게되면 다시 힙의 형태를 갖추어야한다.

 

   1. 맨 뒤에있는 노드를 Root자리로 옮긴다.
   2. 자식 노드중 값이 더 큰 노드와 비교하여 자식 노드가 값이 더 크다면 위치를 바꾼다.
   3. 2번의 작업을 자식노드보다 자신이 클때까지 반복한다.

 

이 또한 그림으로 알아보자.

Root노드가 빠진 상황이다. 이렇게 되면 맨뒤에 있던 노드인 10을 Root로 올린다.

Root로 올리고 자식들과 비교를 시작하게 되는데, 자식 둘중에 44가 더 크므로 44와 비교를 한다. 그런데 44가 10보다 크므로 44와 자리를 바꾼다.

자리를 바꾸고 다시 같은 작업을 반복한다. 11과 13중 13이 크므로 13과 비교한다. 13이 더크므로 자리를 바꾼다.

그 결과 이렇게 힙의 구조를 다시 유지할수 있게 되었다.

 

💡시간복잡도

 삭제도 추가와 거의 유사하게 동작하는 것을 볼 수있다. 결국 이도 마찬가지로 최악의 경우 트리의 제일 깊은곳까지 내려가므로 트리의 높이가 연산 횟수가 되고 따라서 O(logN)의 시간복잡도를 가진다.

 

 

 

🔻우선순위 큐(Priority Queue)

 우선순위 큐는 지금까지 설명한 힙을 이용하여 만든 자료구조이다. 일반적인 큐는 FIFO, 즉 먼저들어온 것이 먼저 나간다는 원칙을 가진 자료구조 이지만, 우선순위 큐는 들어온 순서와는 상관없이, 우선순위가 가장 크거나 작은 자료가 가장 먼저 나간다. 따라서 힙을 이용하여 가장 크거나 작은 자료를 O(1)시간만에 찾아서 내보낼 수 있으므로 Heap을 쓰는 것이 적합하다.

 

🔶구현

 우선순위큐를 구현하면서 위에서 설명한 힙또한 같이 이해할 수 있을 것이다.

우선순위큐는 배열로 구현된 힙을 하나 가지고 있으며,

가장 우선순위가 높은 값을 빼네는 pop(), 자료를 추가하는 push()연산이 존재한다.

 

🔹전체코드

template <typename T>
class PriorityQueue
{
public:

	void push(const T& val)
	{
		_heap->push_back(val);
		int now = _heap->size() - 1;

		while (now > 0)
		{
			int parent = (now - 1) / 2;

			if (_heap[now] < _heap[parent])
				break;

			::swap(_heap[now], _heap[parent]);
			now = parent;
		}
	}

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

	void pop()
	{
		_heap[0] = _heap->back()
		_heap->push_back();
		int now = 0;
		
		while(true)
		{
			int leftChild = now * 2 + 1;
			int rightChild = now * 2 + 2;

			// leaf node일 경우
			if (leftChild >= _heap->size())
				break;

			int next = now;

			if (_heap[leftChild] > _heap[next])
				next = leftChild;

			if (rightChild < _heap->size() && _heap[rightChild] > _heap[next])
				next = rightChild;

			if (next == now)
				break;

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

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

private:
	vector<T>* _heap = {};
	
};

 

🔹push()

큐에 자료를 넣는 작업이다. heap배열에 집어넣고 다시 heap의 구조를 조정하는 과정을 거친다.

void push(const T& val)
{
	_heap->push_back(val);
	int now = _heap->size() - 1;

	while (now > 0)
	{
		int parent = (now - 1) / 2;

		if (_heap[now] < _heap[parent])
			break;

		::swap(_heap[now], _heap[parent]);
		now = parent;
	}	
}

_heap이 vector로 이루어져 있기때문에 push_back을 이용해 힙의 맨뒤에 넣어준다. 그리고 그 인덱스를 now로 설정하여 그림에서 봤던 부모 노드와 비교하여 자리바꾸기 작업을 반복 수행한다.

 

🔹pop()

루트노드를 제거하는 연산이다. 그뒤에는 다시 힙의 구조를 조정하는 과정을 수행한다.

void pop()
{
	_heap[0] = _heap->back()
	_heap->push_back();
	int now = 0;
		
	while(true)
	{
		int leftChild = now * 2 + 1;
		int rightChild = now * 2 + 2;

		// leaf node일 경우
		if (leftChild >= _heap->size())
			break;

		int next = now;

		if (_heap[leftChild] > _heap[next])
			next = leftChild;

		if (rightChild < _heap->size() && _heap[rightChild] > _heap[next])
			next = rightChild;

		if (next == now)
			break;

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

제일 뒤에있는 노드를 루트노드로 바꾸고 자식노드와 비교하면서 자리바꾸기 작업을 반복 수행한다. 여기서 완전 이진트리의 성질로 leftChild = now * 2 + 1이 되고 rightChild = now * 2 + 2이 된다. 비교하는 연산을 수행할 때, 힙이 배열로 구현되어 있으므로 반복을 하다가 인덱스를 벗어날 수 있으므로, 현재 now 노드가 leaf node인지, 자식이 한개인 노드인지, 두개다 있는 노드인지를 나누어서 생각해야한다.

 

1. leaf node일 경우 : 더 이상 비교할게 없으므로 종료한다.

2. 자식 노드가 1개일 경우 : 자식 노드와 비교하여 값이 자식노드가 더 크면 위치를 바꾼다.

3. 자식 노드가 2개일 경우 : 자식 노드중 큰 노드와 자신을 비교하여 자식노드가 더 크면 위치를 바꾼다.

 

이런식으로 경우를 나누어서 구현할 수 있다. 나는 조금 다르게 코드를 짰는데 결국 기본적인 원리는 동일하다.

leaf node이면 반복을 종료하는 것은 똑같고,

1. next라는 변수를 만들어서 일단 now의 값을 넣어놓는다.

2. 그후 next를 leftChild와 비교하여 큰 값의 인덱스로 바꾼다.

3. rightChild가 있다면 그 값과 현재 next 위치에 들어있는 값과 비교하여 큰 값의 인덱스로 바꾼다.

 

여기 까지하면 결국에는 자기 자신과 자식 노드 두개를 모두 비교한 셈이된다.

그 결과 next의 값이 변하지 않고 그대로 now라면 현재 노드의 값이 가장 큰 것이므로 자리를 바꾸지 않고, 반복을 종료한다. 그 반대로 next의 값이 now가 아니라면 그 값과 현재 노드의 자리를 바꾸고, 같은 작업을 반복 수행한다.

 

 

🔻마치며

 이 힙은 나중에 힙 정렬을 할때도 쓰이고, 다익스트라 알고리즘의 성능을 향상시킬수도 있고, 이진 트리의 개념을 확립하는데 굉장히 좋은 자료구조인 것 같다. 또한 우선순위 큐를 직접 구현해보며 힙의 삭제, 추가의 원리를 코드로 짜서 공부해볼 수 있는 좋은 기회였다. 이제 앞으로, A* 길찾기 알고리즘이라든지, 다익스트라 알고리즘에 이 우선순위 큐를 적용시켜 시간복잡도를 낮추는 공부를 해볼 생각이다.