Data Structure Chapter 8. 우선순위큐 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr
우선순위큐추상데이터타입
우선순위큐 우선순위큐 (priority queue) 정의 : 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게됨 스택이나 FIFO 큐를우선순위큐로구현할수있음 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 시뮬레이션시스템 ( 여기서의우선순위는대개사건의시각이다 ) 네트워크트래픽제어 운영체제에서의작업스케쥴링 3
우선순위큐 ADT 객체 : n 개의 element 형의우선순위를가진요소들의모임 연산 create() ::= 우선순위큐를생성한다 init(q) ::= 우선순위큐 q를초기화한다 is_empty(q) ::= 우선순위큐 q가비어있는지를검사한다 is_full(q) ::= 우선순위큐 q가가득찼는가를검사한다 insert(q, x) ::= 우선순위큐 q에요소 x를추가한다 delete(q) find(q) 가장중요한연산은 insert 연산 ( 요소삽입 ), delete 연산 ( 요소삭제 ) 우선순위큐는 2 가지로구분 최소우선순위큐 최대우선순위큐 ::= 우선순위큐로부터가장우선순위가높은요소를삭제하고 이요소를반환한다 ::= 우선순위가가장높은요소를반환한다 4
우선순위큐의구현방법
우선순위큐구현방법 (1/2) 배열을이용한우선순위큐 count 연결리스트를이용한우선순위큐 0 1 2 3 4 5 6 2 5 7 10 12 12 10 7 5 2 NULL 히프 (heap) 를이용한우선순위큐 9 7 5 4 6 3 2 2 1 3 6
우선순위큐구현방법 (2/2) 표현방법에따른연산의복잡도 표현방법 삽입 삭제 순서없는배열 O(1) O(n) 순서없는연결리스트 O(1) O(n) 정렬된배열 O(n) O(1) 정렬된연결리스트 O(n) O(1) 히프 O(logn) O(logn) 7
히프 (heap)
히프 (heap) 란? 히프 (heap) 정의 : 노드들이저장하고있는키들이다음과같은식을만족하는완전이진트리 최대히프 (max heap) 정의 : 부모노드의키값이자식노드의키값보다크거나같은완전이진트리 key( 부모노드 ) key( 자식노드 ) 최소히프 (min heap) 정의 : 부모노드의키값이자식노드의키값보다작거나같은완전이진트리 key( 부모노드 ) key( 자식노드 ) 9 1 7 6 4 2 5 4 3 2 7 5 3 3 2 1 3 7 8 9 < 최대히프 > < 최소히프 > 9
히프의높이 n 개의노드를가지고있는히프의높이는 O(logn) 히프는완전이진트리 마지막레벨 h 을제외하고는각레벨 i 에 2 i 1 개의노드존재 깊이노드의개수 1 1=2 0 2 2=2 1 3 4=2 2 4 3 1 9 2 3 7 6 4 5 6 7 5 4 3 2 8 9 10 2 1 3 10
히프의구현방법 히프는배열을이용하여구현 완전이진트리이므로각노드에번호를붙일수있음 이번호를배열의인덱스라고생각 부모노드와자식노드를찾기가쉬움 왼쪽자식의인덱스 = ( 부모의인덱스 ) 2 오른쪽자식의인덱스 = ( 부모의인덱스 ) 2 + 1 부모의인덱스 = ( 자식의인덱스 )/2 7 5 4 2 1 3 0 1 2 3 4 5 6 7 8 9 10 9 7 6 5 4 3 2 2 1 3 9 2 3 4 5 6 7 8 9 10 1 6 3 2 7 5 4 2 1 3 9 2 3 4 5 6 7 8 9 10 1 6 3 2 0 1 2 3 4 5 6 7 8 9 10 9 7 6 5 4 3 2 2 1 3 왼쪽자식 =(2 3)=6 왼쪽자식 =(2 3)+1=7 11
히프에서의삽입 삽입연산 히프에새로운요소가들어오면새로운노드를히프의마지막노드에이어서삽입 삽입후에새로운노드를부모노드들과교환해서히프의성질을만족 예 ) 회사에서신입사원의능력에따른승진 12
unheap unheap 연산 새로운키 k의삽입연산후히프의성질이만족되지않을수있다 upheap는삽입된노드로부터루트까지의경로에있는노드들을 k와비교, 교환함으로써히프의성질을복원한다 키 k가부모노드보다작거나같으면 upheap는종료한다 히프의높이가 O(logn) 이므로 upheap연산은 O(logn) 이다 9 2 3 7 4 5 6 7 5 4 8 9 10 11 2 1 3 8 1 6 3 2 13
unheap 연산예시 9 2 3 7 4 5 6 7 5 4 8 9 10 11 2 1 3 8 1 6 3 2 9 2 3 7 4 5 6 7 5 8 8 9 10 11 2 1 3 4 1 6 3 2 9 2 3 7 4 5 6 7 5 8 8 9 10 11 2 1 3 4 1 6 3 2 9 2 3 8 4 5 6 7 5 7 8 9 10 11 2 1 3 4 1 6 3 2 14
unheap 알고리즘 insert_max_heap insert_max_heap(a, key) heap_size heap_size + 1; i heap_size; A[i] key; while i 1 and A[i] > A[PARENT(i)] do A[i] A[PARENT(i)]; i PARENT(i); 15
삽입프로그램 insert_max_heap // 현재요소의개수가 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; // 새로운노드를삽입 16
히프에서의삭제 삭제연산 : 최대히프에서의삭제는가장큰키값을가진노드를삭제하는것을의미 루트노드를삭제한다 마지막노드를루트노드로이동시킨다 루트에서부터단말노드까지의경로에있는노드들을교환하여히프성질을만족시킨다 17
downheap 연산예시 히프의높이가 O(logn) 이므로 downheap 연산은 O(logn) 이다 7 5 4 2 1 3 2 3 4 5 6 7 8 9 3 5 4 2 1 7 1 6 3 2 2 3 4 5 6 7 8 9 7 5 4 2 1 3 9 2 3 4 5 6 7 8 9 10 1 1 6 3 2 6 3 2 3 5 4 2 1 7 2 3 4 5 6 7 8 9 5 3 4 2 1 7 1 1 6 3 2 2 3 4 5 6 7 8 9 7 5 4 2 1 3 2 3 4 5 6 7 8 9 1 6 3 2 6 3 2 18
downheap 알고리즘 delete_max_heap delete_max_heap(a) 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[LEFT(i)] > A[RIGHT(i)] then largest LEFT(i); else largest RIGHT(i); if A[PARENT(largest)] > A[largest] then break; A[PARENT(largest)] A[largest]; i CHILD(largest); return item; 19
삭제프로그램 // 삭제함수 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; 20
전체프로그램 (1/2) #include <stdio.h> #define MAX_ELEMENT 200 typedef struct { int key; } element; typedef struct { element heap[max_element]; int heap_size; } HeapType; // 초기화함수 init(heaptype *h) { h->heap_size =0; } 21
전체프로그램 (2/2) void main() { element e1=10, e2=5, e3=30; element e4, e5, e6; HeapType heap; // 히프생성 init(&heap); // 초기화 // 삽입 insert_max_heap(&heap, e1); insert_max_heap(&heap, e2); insert_max_heap(&heap, e3); // print_heap(&heap); } // 삭제 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); 출력 : < 30 > < 10 > < 5 > 22
히프의복잡도분석 삽입연산 삽입연산에서최악의경우, 루트노드까지올라가야하므로트리의높이에해당하는비교연산및이동연산이필요함 O(logn) 삭제연산 삭제에서최악의경우, 가장아래레벨까지내려가야하므로역시트리의높이만큼의시간이걸림 O(logn) 23
히프의응용
히프정렬 히프정렬개요 먼저정렬해야할 n 개의요소들을최대히프에삽입 한번에하나씩요소를히프에서삭제하여저장함 삭제되는요소들은값이증가되는순서 ( 최소히프의경우 ) 대로정렬 수행시간 하나의요소를히프에삽입하거나삭제할때시간이 O(logn) 만큼소요되고요소의개수가 n 개이므로전체적으로 O(nlogn) 시간이걸림 ( 빠른편 ) 특징 히프정렬이가장유용한경우는전체자료를정렬하는것이아니라가장큰값몇개만필요할때 25
히프정렬프로그램 // 우선순위큐인히프를이용한정렬 void heap_sort(element a[], int n) { int i; HeapType h; } init(&h); for(i=0;i<n;i++){ insert_max_heap(&h, a[i]); } for(i=(n-1);i>=0;i--){ a[i] = delete_max_heap(&h); } 26
이산이벤트시뮬레이션 이산이벤트시뮬레이션 이산이벤트시뮬레이션에서모든시간의진행은이벤트의발생에의해서이루어짐 우선순위큐를이용하여이벤트를저장하고이벤트의발생시각을우선순위로하여이벤트를처리함 예 ) 아이스크림가게시뮬레이션 우선순위큐 도착 #5 주문 #2 출발 #1 27
허프만코드 허프만코딩트리 이진트리는각글자의빈도가알려져있는메시지의내용을압축하는데사용될수있다. 이런종류의이진트리를허프만코딩트리라고부른다. A 80 B 16 C 32 D 36 빈도수분석 E 123 F 22 G 16 H 51 I 71...... Z 1 28
허프만코드생성 (1/5) 예를들어, 만약텍스트가 e, t, n, i, s 의 5 개의글자로만이루어졌다고가정하고각글자의빈도수가다음과같다고가정하자. 글자 비트코드 빈도수 비트수 e 00 15 30 t 01 12 24 n 10 8 16 I 110 6 18 s 111 4 12 합계 88 29
허프만코드생성 (2/5) 허프만코드생성절차 빈도수에따라 5 개의글자나열 (s(4), i(6), n(8), t(12), e(15)) 글자 빈도수 e 15 t 12 n 8 i 6 s 4 가장작은빈도수를가지는글자 2 개를추출하고, 이들을단말노드로하여이진트리구성 ( 이때, 루트의값은각자식노드의값을합한값 ) 10 4 6 8 12 15 30
허프만코드생성 (3/5) 허프만코드생성절차 다시글자들의정렬된리스트로돌아가서이합쳐진값을글자들의리스트에삽입하여 (10, 8, 12, 15) 를얻는다. 글자 빈도수 e 15 t 12 n 8 i + s 10 이빈도수를정렬하여 (8, 10, 12, 15) 를얻을수있고, 이중가장작은값 2 개를단말노드로하여다음과같은이진트리구성한다. 18 10 4 6 8 12 15 31
허프만코드생성 (4/5) 허프만코드생성절차 합쳐진값을글자들의리스트에삽입하여빈도수에따라정렬한후, 가장작은값 2 개를단말노드로하여이진트리구성하는작업을반복한다. 18 10 27 4 6 8 12 15 45 18 10 27 4 6 8 12 15 32
허프만코드생성 (5/5) 허프만코드생성절차 이허프만트리에서왼쪽간선은비트 1 을나타내고오른쪽간선은비트 0 을나타낸다. 45 1 18 1 1 0 10 27 0 0 1 0 4 6 8 12 15 33
허프만코드프로그램 (1/6) #define MAX_ELEMENT 100 typedef struct TreeNode { int weight; struct TreeNode *left_child; struct TreeNode *right_child; } TreeNode; typedef struct { TreeNode *ptree; int key; } element; typedef struct { element heap[max_element]; int heap_size; } HeapType; 34
허프만코드프로그램 (2/6) // 초기화함수 init(heaptype *h) { h->heap_size =0; } // 삽입함수 void insert_min_heap(heaptype *h, element item) { // 30page 참조 } // 삭제함수 element delete_min_heap(heaptype *h) { // 31page 참조 } 35
허프만코드프로그램 (3/6) // 이진트리생성함수 TreeNode *make_tree(treenode *left, TreeNode *right) { TreeNode *node= (TreeNode *)malloc(sizeof(treenode)); if( node == NULL ){ fprintf(stderr," 메모리에러 \n"); exit(1); } node->left_child = left; node->right_child = right; return node; } // 이진트리제거함수 void destroy_tree(treenode *root) { if( root == NULL ) return; destroy_tree(root->left_child); destroy_tree(root->right_child); free(root); } 36
허프만코드프로그램 (4/6) // 허프만코드생성함수 void huffman_tree(int freq[], int n) { int i; TreeNode *node, *x; HeapType heap; element e, e1, e2; init(&heap); for(i=0;i<n;i++){ node = make_tree(null, NULL); e.key = node->weight = freq[i]; e.ptree = node; insert_min_heap(&heap, e); } 37
허프만코드프로그램 (5/6) for(i=1;i<n;i++){ // 최소값을가지는두개의노드를삭제 e1 = delete_min_heap(&heap); e2 = delete_min_heap(&heap); // 두개의노드를합친다 x = make_tree(e1.ptree, e2.ptree); e.key = x->weight = e1.key + e2.key; e.ptree = x; insert_min_heap(&heap, e); } e = delete_min_heap(&heap); // 최종트리 destroy_tree(e.ptree); } 38
허프만코드프로그램 (6/6) // 주함수 void main() { int freq[] = { 15, 12, 8, 6, 4 }; huffman_tree(freq, 5); } 39