[CS과목/자료구조] 09 우선순위 큐

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외)

 

9.1 우선순위 큐 추상 데이터 타입

우선순위 큐의 소개

 우선순위 큐는 우선순위의 개념을 큐에 도입한 자료구조이다. 보통의 큐는 선입 선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 된다. 그러나 우선순위 큐(priority queue)에서는 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다. 히프(heap)구조가 우선순위 큐를 가장 효율적으로 구현할 수 있다. 우선순위 큐는 2가지로 구분할 수 있는데, 최소 우선순위 큐는 가장 우선순위가 낮은 요소를 먼저 삭제한다. 최대 우선순위 큐는 반대로 가장 우선순위가 높은 요소가 먼저 삭제된다.

 

9.2 우선순위 큐의 구현 방법

히프를 사용하는 방법

 히프(heap)는 완전 이진 트리의 일종으로 우선순위 큐를 위하여 특별히 만들어진 자료 구조이다. 히프는 일종의 느슨한 정렬 상태를 유지한다. 즉, 완전히 정렬된 것은 아니지만 전혀 정렬이 안된 것도 아닌 상태를 유지한다.

 

9.3 히프

히프의 개념

 히프(heap)는 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조이다. 히프는 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리를 말한다. 히프트리에서는 중복된 값을 허용함에 유의하라. 이진 탐색 트리에서는 중복된 값을 허용하지 않았다. 히프의 목적은 삭제 연산이 수행될 때마다 가장 큰 값을 찾아내기만 하면 되는 것이므로(가장 큰 값은 루트 노드에 있다.) 전체를 정렬할 필요는 없다.

 

히프의 종류

 히프에는 두 가지 종류의 히프트리가 존재한다. 하나는 부모 노드의 키 값이 자식 노드보다 큰 최대 히프(max heap), 또 하나는 반대로 노드의 키 값이 자식 노드보다 작은 최소 히프(min heap)이다. 여기서는 편의상 최대 히프만을 다루기로 한다.

 

히프의 구현

 히프는 완전 이진 트리이기 때문에 각각의 노드에 그림에서처럼 차례대로 번호를 붙일 수 있다. 이 번호를 인덱스로 생각하면 배열에 히프의 노드를 저장할 수 있다. 따라서 히프를 저장하는 표준적인 자료구조는 배열이다. 프로그램 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.

 

9.4 히프의 구현

히프의 정의

 히프는 1차원 배열로 표현될 수 있기 때문에 아래와 같이 히프의 각 요소들을 구조체 element로 정의하고, element의 1차원 배열을 만들어 히프를 구현한다.

#define MAX_ELEMENT 200

typedef struct {
	int key;
} element;

typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size;
} HeapType;

 

삽입 연산

 히프에 새로운 요소가 들어오면, 일단 새로운 노드를 히프의 마지막 노드로 삽입한다. 마지막 노드 다음에 새로운 노드를 위치시키면 히프트리의 성질이 만족되지 않을 수 있다. 따라서 삽입 후에 새로운 노드를 부모 노드들과 교환해서 히프의 성질을 만족시켜 주어야 한다.

void insert_max_heap(HeapType* h, element item)
{
	int i;
	i = ++(h->heap_size);

	// 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
	while ((i != 1) && (item.key > h->heap[i / 2].key)) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item; // 새로운 노드를 삽입

}

 

히프의 삭제 연산

 최대 히프에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다. 최대 히프에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다. 루트 노드 삭제 후에 히프를 재구성하는 것이 필요하게 된다. 마지막 노드를 루트 노드에 위치한 다음 자식 노드와 교환하며 히프의 성질을 만족시킨다.

// 삭제 함수
element delete_max_heap(HeapType* h)
{
	int parent, child;
	element item, temp;

	item = h->heap[1];
	temp = h->heap[(h->heap_size)--];
	parent = 1;
	child = 2;

	while (child <= h->heap_size) {
		// 현재 노드의 자식노드중 더 큰 자식노드를 찾는다.
		if ((child < h->heap_size) &&
			(h->heap[child].key) < h->heap[child + 1].key)
			child++;
		if (temp.key >= h->heap[child].key) break;
		
		// 한단계 아래로 이동
		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}

	h->heap[parent] = temp;
	return item;
}