[자료구조] 우선순위 큐와 힙

Priority queue

• 우선순위를 가진 항목들을 저장하는 큐
• FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다.
• 스택이나 큐(FIFO)를 우선순위 큐로 구현할 수 있다.
• 스택 -> 가장 최근에 들어온 데이터가 삭제 ( 시간이 우선순위 )
• 큐 -> 가장 먼저 들어온 데이터가 삭제 ( 시간이 우선순위 )
• 우선순위 큐 -> 가장 우선순위가 높은 데이터

최소 우선순위 큐

최대 우선순위 큐가 존재

 

우선순위 큐의 추상자료형 (Abstract Data Type)

객체

• n개의 element형의 우선순위를 가진 요소

연산

• create() : 우선순위 큐를 생성
• init(q) : 우선순위 큐 q를 초기화
• is_empty(q) : 우선순위 큐 q가 비어있는지를 검사
• is_full(q) : 우선순위 큐 q가 가득 찼는지 검사
• insert(q, x) : 우선순위 큐 q에 요소 x를 추가
• delete(q) : 우선순위 큐 q에 가장 우선순위가 높은 요소를 삭제하고 반환

 

우선순위 큐 구현 방법

• 배열(array)을 이용
• 연결리스트(linked list)를 이용
• 힙(heap)를 이용

 

정렬된 배열로 구현

• 우선순위를 기준으로 오름차순 정렬하자.
• 그럼 가장 우선순위가 큰 데이터는 배열의 마지막에 위치한다.
• 삽입함수는 삽입 위치를 찾아야 하는데 키 값을 기준으로 처음부터 삽입 위치를 탐색
  • 위의 삽입위치 찾는 시간 복잡도 : O(n)
  • 해당 위치에 키 입력을 위한 데이터 이동이 필요하니 시간 복잡도 : O(n)
  • 따라서 시간 복잡도 : O(n)
• 삭제함수는 마지막 데이터를 반환하고 배열 데이터의 개수를 하나 줄인다.
  • 삭제 시, 시간 복잡도 : O(1) (맨 뒤의 요소를 삭제하니깐)

 

정렬 안된 배열로 구현

• 삽입 함수는 새로운 데이터를 무조건 배열 끝에 붙이자.( 안 그러면 이동을 시켜줘야 함 )
  • 삽입의 시간 복잡도 : O(1)
• 삭제 함수는 삭제할 데이터를 찾는 과정이 필요하다.
  • 삭제 시, 가장 높은 우선 순위를 처음부터 끝까지 탐색해야 함.
  • 시간 복잡도 : O(n)
  • 따라서 시간 복잡도 : O(n)

 

정렬 안된 배열과 정렬된 배열의 비교

• 정렬된 배열과 정렬 안된 배열을 사용할 때 삽입, 삭제 시간 복잡도가 뒤바뀐 모습
• 따라서 삭제가 빨라야 한다면 정렬된 배열을 사용
• 삽입이 빨라야 한다면 정렬 안된 배열을 사용
• 삽입, 삭제 전체를 감안하면 두 방법 다 O(n)의 시간 복잡도.

 

정렬된 연결 리스트로 구현

• 우선순위를 기준으로 내림차순으로 정렬하자.
• 우선순위가 가장 높은 데이터는 헤드 포인터가 직접 가리킨다.
• 삭제의 시간 복잡도 : O(1)
• 삽입 함수는 키 값을 기준으로 삽입 위치를 찾아야 한다.
  • 삽입 위치가 마지막일 경우가 최악의 경우이므로 시간 복잡도 : O(n)
• 배열처럼 삭제 시 이동은 불필요하다. 포인터만 변경하면 됨
• 삭제와 삽입 모두 감안한 시간 복잡도는 O(1) + O(n) = O(n) 이다.

 

정렬 안된 연결 리스트로 구현

• 삽입할 데이터를 가장 첫 노드에 삽입 ( 뒤에 하려면 N번 탐색해야 하기 때문 )
  • 삭제의 시간 복잡도 : O(1) 
• 배열처럼 이동은 불필요 포인터만 바꾸자
• 삭제를 위해 가장 큰 데이터를 처음부터 마지막까지 탐색해야 함.
  • 탐색의 시간 복잡도 : O(n)
• 삽입과 삭제를 감안한 시간 복잡도 : O(1) + O(n) = O(n)

 

구현 방법에 따른 성능 비교

구현 방법	삽입	삭제
정렬 안된 배열	O(1)	O(n)
정렬 안된 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결 리스트	O(n)	O(1)
힙(heap)	O(logn)	O(logn)

-> 데이터가 1000개일 때, O(n) 알고리즘은 1000초, O(logN) 알고리즘은 약 10초 (log2에1000은 약 10)

 

 

힙(heap)

• 우선순위 큐를 위해 만들어진 자료구조이다.
• 힙의 키들은 다음을 만족하는 완전 이진 트리(complete binary tree)이다.

 

최대 힙(max heap)

• 부모 노드의 키 값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리
• key(부모노드) >= key(자식노드)

최대 힙

 

최소 힙(min heap)

• 부모 노드의 키 값이 자식 노드의 키값보다 작거나 같은 안전 이진 트리
• key(부모노드) <= key(자식노드)

최소 힙

 

힙의 높이

• n개의 노드를 가지고 있는 힙의 높이는 logn이다.
• 왜냐 힙은 완전이진트리이기 때문.

-> 마지막 레벨 h를 제외하고는 각 레벨 i에 2^(i-1)개의 노드가 존재한다.

 

힙의 구현 (배열)

• 힙은 완전이진트리이므로 각 노드에 번호를 붙일 수 있다.
• 이 번호를 인덱스라고 생각하자.
• 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2
• 오른쪽 자식의 인덱스 = (부모의 인덱스*2)+1
• 부모의 인덱스 = 자식의 인덱스/2

인덱스 0	인덱스1	인덱스2	인덱스3	인덱스4	인덱스5	인덱스6	인덱스7	인덱스8	인덱스9	인덱스10
	9	7	6	5	4	3	2	2	1	3

 

힙 구현을 위한 구조체

#define MAX_ELEMENT 200
typedef struct {
	int key;
} element;

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

 

힙 삽입의 원리 ( 최대 힙의 경우 )

• 힙에 새로운 요소를 넣으면, 일단 새로운 요소를 마지막 노드에 이어서 삽입
• 삽입 후, 새로운 노드를 부모 노드들과 비교, 교환을 통해 적절한 자리에 이동
• 이동의 종료는 새로운 노드의 key가 부모 노드보다 작거나 같으면 종료
• 힙의 높이가 O(logn)이므로 힙의 삽입 연산 또한 O(logn)이다.

(삽입 순서)

 

삽입 함수

void insert_max_heap(HeapType* h, element item)
{
	// 삽입할 위치는 현재 노드의 개수+1 인덱스이다.
	int i = ++(h->heap_size);

	// i!=1 -> i가 1이라면 첫 삽입이므로 while문 안들어가기
	while (i != 1 && item.key > h->heap[i / 2].key)
	{
		h->heap[i] = h->heap[i / 2]; // 부모노드의 key를 끌어내려 복사함
		i /= 2; // 현재 인덱스를 부모 노드의 인덱스로 이동
	}

	h->heap[i] = item;
}

 

힙 삭제의 원리

• 최대 힙에서 삭제는 가장 큰 키값을 가진 노드를 뽑아내는것임 -> 루트 노드의 삭제를 의미
• 루트 노드의 삭제 이후, 그 자리는 마지막 노드로 대체한다.
• 마지막 노드로 대체했을 경우 힙의 모습에 어긋나니 대체한 노드를 적절한 위치까지 내려간다.
• 그리하여 힙의 성질을 만족하게 만듦.
• 힙의 높이가 O(logn)이므로 힙의 삭제 연산 또한 O(logn)이다.

(삭제 순서 그림)

 

힙 삭제 함수

element delete_max_heap(HeapType* h)
{
	int parent, child;
	element item, temp;

	
	item = h->heap[1]; // 삭제할 노드
	temp = h->heap[(h->heap_size)--]; // 맨 마지막 노드를 이용해 힙을 다시 완전하게 만들기

	// 1번 인덱스부터 내려가며 가능한 자리를 찾아감
	parent = 1;
	child = 2;

	/* child로 내려갈 수 있는지 확인하면서 쭉쭉 내려갈건데
	* 내려갈려면 child가 현재 노드 개수보다 작아야함
	* 결과적으로 parent가 바꿀 수 있는 노드를 가리키게 됨
	*/
	while (child <= h->heap_size)
	{ // 이 while문을 들어온건 일단 child가 존재하기에 현재 자리와 비교를 해봐야 한다는것

		// 오른쪽 노드가 존재하고 그 노드의 우선순위가 더 크면 그쪽 노드로 이동
		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;

}

 

최대 힙 구현한 코드 전체 테스트

#include <stdio.h>
#include <stdlib.h>
#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)
{
	// 삽입할 위치는 현재 노드의 개수+1 인덱스이다.
	int i = ++(h->heap_size);

	// i!=1 -> i가 1이라면 첫 삽입이므로 while문 안들어가기
	while (i != 1 && item.key > h->heap[i / 2].key)
	{
		h->heap[i] = h->heap[i / 2]; // 부모노드의 key를 끌어내려 복사함
		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)--]; // 맨 마지막 노드를 이용해 힙을 다시 완전하게 만들기

	// 1번 인덱스부터 내려가며 가능한 자리를 찾아감
	parent = 1;
	child = 2;

	/* child로 내려갈 수 있는지 확인하면서 쭉쭉 내려갈건데
	* 내려갈려면 child가 현재 노드 개수보다 작아야함
	* 결과적으로 parent가 바꿀 수 있는 노드를 가리키게 됨
	*/
	while (child <= h->heap_size)
	{ // 이 while문을 들어온건 일단 child가 존재하기에 현재 자리와 비교를 해봐야 한다는것

		// 오른쪽 노드가 존재하고 그 노드의 우선순위가 더 크면 그쪽 노드로 이동
		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;

}

HeapType* create()
{
	return (HeapType*)malloc(sizeof(HeapType));
}

void init(HeapType* h)
{
	h->heap_size = 0;
}

int main(void)
{

	element e1 = { 10 }, e2 = { 5 }, e3 = { 30 };
	element e4, e5, e6;
	HeapType* heap=create();
	init(heap);

	insert_max_heap(heap, e1);
	insert_max_heap(heap, e2);
	insert_max_heap(heap, e3);

	e4 = delete_max_heap(heap);
	printf("[%d] ", e4.key);
	e5 = delete_max_heap(heap);
	printf("[%d] ", e5.key);
	e6 = delete_max_heap(heap);
	printf("[%d]", e6.key);
	free(heap);
}

힙에 10 -> 5 -> 30 순서대로 삽입

 

(실행 결과)

 

힙의 삽입에서 최악의 경우 루트 노드까지 올라가므로 힙의 높이에 해당하는 비교 연산 및 이동이 필요하다.

즉, 힙의 삽입 -> O(logN)

 

힙의 삭제에서 최악의 경우, 가장 아래 레벨까지 내려가야 하므로 힙의 높이만큼 시간이 걸림

즉, 힙의 삭제 -> O(logN)

 

힙 정렬

• 최대 힙에서 삭제하면 가장 큰 원소가 삭제가 된다.
• 이것을 계속 뽑아내 순차적으로 저장해 가면 정렬된 결과가 나온다.
• 내림차순 : 최대 힙을 이용한다.
• 오름차순 : 최소 힙을 이용한다.
• 하나의 요소를 삭제할 때 O(logN)이고 요소가 n개 이므로 전체적으로 O(nlogn)이다.
• 힙 정렬이 유용할 땐 전체 자료를 정렬할 때가 아닌 가장 큰 값 몇 개만 뽑아낼 때이다.
• 힙을 사용하는 정렬은 힙 정렬하고 한다.

 

최대 힙을 이용한 오름차순 정렬 함수

void heap_sort(element a[], int n)
{

	HeapType* h = create();
	init(h);

	printf("정렬전 배열\n");
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");


	for (int i = 0; i < n; i++)
		insert_max_heap(h, a[i]);

	for (int i = n - 1; i >= 0; i--)
	{
		a[i] = delete_max_heap(h);
	}

	printf("정렬 후 배열\n");
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);

}

 

main에서는 아래와 같이 힙 정렬을 부른다.

printf("\n");
element a[7] = { {2},{5},{2},{6},{1},{8},{9} };
heap_sort(a, 7);

 

실행 결과

 

 

 

사실 아래와 같이 저장하면 내림차순으로도 정렬, 저장이 가능하다.

for (int i = 0; i <n; i++)
{
	a[i] = delete_max_heap(h);
}

 

실행 결과