[자료구조] 우선순위 큐 (priority queue), 히프의 삽입과 삭제

우선순위 큐 (priority queue)

우선순위 큐는 우선순위를 가진 항목들을 저장하는 큐입니다.

일반적으로 큐는 선입선출(FIFO)기반의 자료구조로 알려져있는데 우선순위 큐는 우선순위가 높은 데이터가 먼저 나가게 됩니다. (ex. 구급차, 소방차가 다른 차들보다 먼저 나가는 일)

 

우선순위 큐의 종류에는 최소 우선순위 큐와 최대 우선순위 큐가 있으며 구현방법에는 배열, 연결리스트, 히프(heap)가 있습니다.

 

우선순위 큐의 구현방법 - 배열

우선 순위큐는 완전 이진 트리이므로 각 노드에 순서대로 번호를 붙일 수 있습니다. 붙여진 번호가 배열의 인덱스인 것입니다. 

배열을 이용하여 트리를 구현하는 방법과 동일합니다. 배열을 이용하면 다음과 같은 규칙에 의해서 부모노드와 자식노드를 찾기가 쉽습니다.

- 왼쪽 자식의 인덱스 = (부모의 인덱스)*2

- 오른쪽 자식의 인덱스 = (부모의 인덱스)*2 + 1

- 부모의 인덱스 = (자식의 인덱스)/2

 

우선순위 큐의 구현방법 - 히프

히프는 최대 히프와 최소 히프가 존재합니다.최대 히프란, 부모 노드의 키가 자식 노드의 키보다 크거나 같은 완전 이진 트리입니다.최소 히프란, 부모 노드의 키가 자식 노드의 키보다 작거나 같은 완전 이진 트리입니다.

 

먼저 히프의 높이를 계산하는 방법입니다.

노드 수가 n개일 때 완전 이진 트리의 높이는 log2(n+1)입니다 (2는 로그의 밑)

각 레벨 i에는 2^(i-1) 개의 노드가 존재할 수 있습니다. (마지막 레벨 주의)

 

10개의 데이터를 저장하고 있는 히프의 높이는? 

  - log2(8) < log2(11) < log2(16) 이므로 4입니다.
20개의 데이터를 저장하고 있는 히프의 높이는? 

  - log2(16) < log2(21) < log2(32) 이므로 5입니다.
30개의 데이터를 저장하고 있는 히프의 높이는? 

  - log2(16) < log2(31) < log2(32) 이므로 5입니다.
100개의 데이터를 저장하고 있는 히프의 높이는? 7

  - log2(64) < log2(101) < log2(128) 이므로 7입니다.
1000개의 데이터를 저장하고 있는 히프의 높이는? 10

  - log2(512) < log2(1001) < log2(1024) 이므로 10입니다.

 

우선순위 큐의 연산

create() : 우선 순위큐를 생성한다.

init(q) : 우선 순위큐 q를 초기화한다.

is_empty(q) : 우선 순위큐 q가 비어있는지를 검사한다.

is_full(q) : 우선 순위큐 q가 가득 찼는가를 검사한다.

insert(q, x) : 우선 순위큐 q에 요소 x를 추가한다. ★

delete(q) : 우선 순위큐로부터 가장 우선순위가 높은 요소를 삭제 후 반환한다. ★

find(q) : 우선 순위가 가장 높은 요소를 반환한다.

 

히프의 삽입 연산

(1) 새로운 노드를 히프의 마지막에 삽입합니다.

(2) 새로운 노드를 부모 노드들과 교환해서 히프의 종류에 따른 조건을 성립합니다.

 

최대 히프 삽입 연산

// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다.
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;     // 새로운 노드를 삽입
}

 

히프의 삭제 연산

최대 히프를 기준으로 키 값이 가장 큰 노드(루트 노드)를 삭제합니다. 회사에서 사장이 떠나면 적절한 서열을 다시 매기는 것과 비슷한 원리입니다. 가장 말단 사원(완전 이진트리의 마지막 index 노드)을 사장 자리로 올린 후 능력에 따라 강등합니다.

 

최대 히프 삭제 연산

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 ) // 마지막 노드와 key가 같으면
		break;
	  h->heap[parent] = h->heap[child];
	  parent = child; child *= 2; // 한단계 아래로 이동
    }
    h->heap[parent] = temp; // temp를 연결
    return item;
 }

 

연습문제

삽입 연산 연습문제 01 | 빈 max heap에 다음 키들을 순서대로 삽입한 결과를 트리로 보여라.

12, 14, 26, 38, 29, 40, 55, 57, 8, 66

삽입 연산 연습문제 02 | 빈 max heap에 다음 키들이 순서대로 삽입 되어있다. 8, 7, 6, 5. 루트 노드를 A라 한다.

| insert_max_heap(A, 9)를 호출 시 while문 진입 횟수는?

2

| 9를 삽입 후 insert_max_heap(A, 3) 을 호출 시 while문 진입 횟수는?

0

삽입 연산 연습문제 03 | 빈 max heap에 다음 키들이 순서대로 삽입 되어있다. 90, 70, 50, 10, 30, 20, 40, 5, 2, 1. 루트 노드를 A라 한다.

| insert_max_heap(A, 25)를 호출 시 while문 진입 횟수와 그 때의 i값은?

while 0번, i = 11

| 25 삽입 후 insert_max_heap(A, 55)를 호출 시 while문 진입 횟수와 그 때의 i값은?

while 2번, i = 3

| 55 삽입 후 insert_max_heap(A, 93)를 호출 시 while문을 2번만 마친 트리의 상태와 그 때의 i값은?

i = ++12 = 13인 상태에서

key 93이 heap[13/2=6]의 50보다 크므로 heap[13]자리에 50을 넣는다. 그리고 i값은 13/2=6이 된다. (while문 1회 종료)

key 93이 heap[6/2=3]의 55보다 크므로 heap[6]자리에 55를 넣는다. 그리고 i값은 6/2=3이 된다. (while문 2회 종료)

 

삭제 연산 연습문제 01 | 빈 max heap에 다음 키들이 순서대로 삽입 되어있다. 5, 1, 3, 4. 루트 노드를 A라 한다.

| delete_max_heap(A) 호출 시 트리의 상태와 while문 반복 횟수와 그 때의 i값은?

delete_max_heap(A): // pseudo code입니다.

item ← A[1];
A[1] ← A[heap_size];
heap_size←heap_size-1;
i ← 2;
while i ≤ heap_size do
	if i < heap_size and A[i+1] > A[i]
		then largest ← i+1;
		else largest ← i;
	if A[PARENT(largest)] > A[largest] 
		then break;
	A[PARENT(largest)] ↔ A[largest];
	i ← LEFT_CHILD(largest);

return item;

while문 1회, i = 4

 

삭제 연산 연습문제 02 | 빈 max heap에 다음 키들이 순서대로 삽입 되어있다. 70, 60, 50, 4, 5, 1, 3, 80. 루트 노드를 A라 한다.

| delete_max_heap(A) 호출 시 트리의 상태와 while문 반복 횟수와 그 때의 i값은?

 

삭제 연산 연습문제 03 | 다음 max heap에 관하여 물음에 답하라.

| delete_max_heap(HeapType *h) 호출 시 트리의 상태와 while문 반복 횟수와 그 때의 child값은?

| 다시 한번 delete_max_heap(HeapType *h) 호출 시 트리의 상태와 while문 반복 횟수와 그 때의 child값은?