[열혈자료구조] 9강. 우선순위 큐(Priority Queue)와 힙(heap)

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

 

우선순위 큐(Priority Queue)란?

우선순위 큐 또한 큐와 마찬가지로 enqueue, dequeue 연산이 있으나, 연산의 결과에서 차이를 보인다. 뒤에서 데이터를 enqueue하고 앞에서 dequeue 하는 큐와 달리, 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. 프로그래머가 결정한 기준에 따라 데이터에 우선순위를 매기고, 해당 순서에 따라 데이터를 꺼낼 수 있도록 하는 것이다. 우선순위 큐는 아래 세 가지 방법으로 구현한다.

1. 배열을 기반으로 구현
2. 연결 리스트를 기반으로 구현
3. 힙(heap)을 기반으로 구현

배열을 기반으로 구현

 

배열을 기반으로 구현하면, 우선순위가 높은 데이터를 배열의 앞쪽에, 우선순위가 낮은 데이터를 배열의 뒤쪽에 위치시킬 수 있다. 그러나, 이런 방식으로 구현하면 데이터를 삽입/삭제할 때 데이터를 한 칸씩 밀어야 하는 상황이 생기므로 매우 비효율적이다. 

 

연결 리스트를 기반으로 구현

 

연결 리스트를 기반으로 구현하면, 배열처럼 데이터를 한 칸씩 밀어야 하는 상황은 생기지 않지만, 삽입 위치를 찾기 위해 첫 노드에서부터 한 노드씩 비교해 가며 우선순위를 비교해야 한다. 이는 배열 또한 가지고 있는 문제이다.

 

이러한 두 가지 구현 방식의 문제로 인해, 우선순위 큐는 "힙" 이라는 새로운 자료구조를 이용해 구현한다.

 

힙(Heap)이란?

힙(Heap): 완전 이진 트리의 일종으로, 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 우선순위가 크거나 같은 구조

예를 들어, "숫자의 크기"를 우선순위의 기준으로 잡는다면, 아래와 같이 "최대 힙(max heap)"이 만들어진다. 반대로, 작을수록 우선순위를 부여한다면 "최소 힙(min heap)"도 만들 수 있다.

 

힙의 구현

힙에서의 데이터 저장

 

위 그림의 힙에 새로운 데이터 70을 저장한다고 하자. 이때 전략은, 먼저 마지막 위치에 새로운 데이터를 저장하고, 부모 노드와 우선순위를 비교하여 위치가 바뀌어야 한다면 바꾸는 것을 반복하는 것이다.

힙에서의 데이터 삭제

 

힙에서 데이터 삭제는 루트 노드의 삭제 방법을 알면 나머지 노드는 재귀적으로 삭제할 수 있다. 루트 노드의 삭제는 아래와 같은 알고리즘을 사용할 수 있다.

 

루트 노드를 삭제하고, 마지막 노드를 루트로 올린 뒤, 제자리를 찾아가도록 한다.

 

아래와 같은 힙에서 루트 노드 "100"을 삭제한다고 해 보자.

 

300을 삭제하면, 마지막 terminal node 중 하나인 "20"을 루트 자리에 올리고, 자식 노드와 비교를 하고 우선순위에 따라 바꿔치기를 하면서 제 위치를 찾아가도록 하는 것이다.

---

이러한 세 가지 구현(배열, 연결 리스트, 힙)에서 삽입과 삭제의 시간 복잡도를 비교하면 아래와 같다.

 

그렇다면 힙은 배열과 연결 리스트 중 어떤 것으로 구현해야 할까? 일반적으로 힙은 배열로 구현한다. 그 이유는, 연결 리스트로 힙을 구현하면 새로운 노드를 추가하기가 쉽지 않기 때문이다. 따라서, 배열 기반으로 힙을 구현하고, 아래와 같이 노드에 번호를 매기면 된다. 그러면 번호에 일련의 규칙성이 보일 것이다.

즉, 루트 노드에 1을 할당하고, 자식 노드로 내려갈 때 x2를 하거나 x2 +1 을 하면 해당 노드의 번호를 알 수 있다. 그리고 거꾸로, 자식에서 부모로 갈 때는 2로 나눈 값을 버림하면 된다. 또한, 인덱스 0은 비워 두어야 한다. 이 인덱싱 아이디어는 한동안 대학수학능력시험 수학 영역 수I 파트(2015개정)에서 수열 킬러 단골 소재로 등장하기도 했다. 궁금한 사람은 풀어보도록 하자

출처: 한국교육과정평가원

이제 힙 구현을 위한 헤더 파일을 살펴 보자.

#ifndef __SIMPLE_HEAP_H__
#define __SIMPLE_HEAP_H__

#define TRUE	1
#define FALSE	0

#define HEAP_LEN	100

typedef char HData;
typedef int Priority;

typedef struct _heapElem
{
	Priority pr;
	HData data;
} HeapElem;

typedef struct _heap
{
	int numOfData;
	HeapElem heapArr[HEAP_LEN];
} Heap;


void HeapInit(Heap * ph);
int HIsEmpty(Heap * ph);

void HInsert(Heap * ph, HData data, Priority pr);
HData HDelete(Heap * ph);

#endif

 

heapElem 구조체에는 데이터(data)와 우선순위(priority)값이 들어간다. Priority 값이 작을수록 높은 우선순위인 것이다. 여기서 HeapInit, HIsEmpty는 다소 뻔하게 구현할 수 있으므로, 데이터의 삽입과 삭제를 중심으로 구현해 보자. 먼저 계산의 편의를 위해, 부모/자식 노드의 인덱스를 가져오는 아래 세 함수를 정의하였다.

int GetParentIDX(int idx) 
{ 
	return idx/2; 
}

int GetLChildIDX(int idx) 
{ 
	return idx*2; 
}

int GetRChildIDX(int idx) 
{ 
	return GetLChildIDX(idx)+1; 
}

 

또한, 두 자식 노드 중 더 높은 우선순위를 가지는 자식의 인덱스 값을 반환하는 함수를 정의하였다. 즉, 자식 노드가 존재하지 않는다면(terminal node 라면) 0을 반환하고, 왼쪽 자식 노드 하나만 존재한다면 그 인덱스를 반환하며, 둘 다 존재한다면 비교하여 왼쪽과 오른쪽 중 우선순위가 큰 것의 인덱스를 반환한다.

int GetHiPriChildIDX(Heap * ph, int idx)
{
	if(GetLChildIDX(idx) > ph->numOfData)
		return 0;

	else if(GetLChildIDX(idx) == ph->numOfData)
		return GetLChildIDX(idx);

	else
	{
		if(ph->heapArr[GetLChildIDX(idx)].pr 
						> ph->heapArr[GetRChildIDX(idx)].pr)
			return GetRChildIDX(idx);
		else
			return GetLChildIDX(idx);
	}
}

 

삭제 함수: HDelete

 

HDelete는 앞서 설명한 대로, 먼저 루트 노드(heapArr[1])를 삭제하는 것으로 시작된다. retData라는 변수에 루트가 가지고 있던 데이터를 저장하고, terminal node 중 가장 인덱스가 큰 것을 루트 자리로 올린다고 생각한다. 그리고 자식 노드 중 우선순위가 부모보다 큰 것이 있으면 안 되므로, GetHiPriChildIDX 함수를 이용하여 자식 중 우선순위가 큰 것과 계속 바꿔치기한다. 그리고 이동이 끝나면, 마지막 노드를 최종 저장하고 끝낸다.

HData HDelete(Heap * ph)
{
	HData retData = (ph->heapArr[1]).data;
	HeapElem lastElem = ph->heapArr[ph->numOfData];

	int parentIdx = 1;  
	int childIdx;

	while(childIdx = GetHiPriChildIDX(ph, parentIdx))
	{
		if(lastElem.pr <= ph->heapArr[childIdx].pr)
			break;

		ph->heapArr[parentIdx] = ph->heapArr[childIdx];
		parentIdx = childIdx;
	}

	ph->heapArr[parentIdx] = lastElem;
	ph->numOfData -= 1;
	return retData;
}

 

즉, HDelete는 마지막 노드가 있어야 하는 새로운 위치를, 부모의 인덱스를 갱신해 가며 찾는 것이다.

삽입 함수: HInsert

 

삽입 함수도 앞서 설명한 대로, 일단 가장 마지막 노드에 저장하고, 부모와 우선 순위를 비교하여 위로 올리는 것이다. 새 노드가 저장될 인덱스 값을 찾고, 해당 위치에 노드를 생성 및 초기화한다. 그리고 새 노드와 부모의 우선순위를 비교하여, 새 노드가 더 높다면 부모의 노드를 하나 내리고 새 노드를 올린다. 이때, 부모 노드는 실제로 노드의 인덱스를 변경하지만, 새 노드는 인덱스를 저장한 변수 idx만 바꾼다. 그리고 while문이 끝났을 때 한꺼번에 저장한다.

void HInsert(Heap * ph, HData data, Priority pr)
{
	int idx = ph->numOfData+1;
	HeapElem nelem = {pr, data}; 

	while(idx != 1)
	{
		if(pr < (ph->heapArr[GetParentIDX(idx)].pr))
		{
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
		}
		else
			break;
	}
	
	ph->heapArr[idx] = nelem;
	ph->numOfData += 1;
}

---

이러한 구현에서, 일반적인 상황에서는 데이터를 알고 있는 경우는 있어도 데이터의 우선순위를 계산하여 노드에 추가하기는 까다로운 경우들이 존재한다. 그렇기 때문에, 아래와 같은 구조체의 정의는 우선순위를 노드를 정의할 때 직접 입력받아야 한다는 점에서 불편하다.

typedef struct _heapElem
{
	Priority pr;
	HData data;
} HeapElem;

typedef struct _heap
{
	int numOfData;
	HeapElem heapArr[HEAP_LEN];
} Heap;

 

따라서, 우선순위를 값으로서 직접 전달하는 것이 아니라, 우선순위를 결정하는 함수를 전달하는 방식으로 아래와 같이 구조체를 변경할 수도 있다. 아예 heapElem을 없애고, PriorityComp라는 비교 식을 넣는 것이다.

typedef struct _heap
{
	PriorityComp * comp;
	int numOfData;
	HData heapArr[HEAP_LEN];
} Heap;

 

이때 PriorityComp는 아래와 같이 선언한다.

typedef int PriorityComp(HData d1, HData d2);