슬라이드 1

Transcription

1 CHAP 8: 우선순위큐

2 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다.

3 우선순위큐 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템 ( 여기서의우선순위는대개사건의시각이다.) 네트워크트래픽제어 운영체제에서의작업스케쥴링

4 우선순위큐 ADT 객체 : n개의 element형의우선순위를가진요소들의모임 연산 : create() ::= 우선순위큐를생성한다. init(q) ::= 우선순위큐 q를초기화한다. is_empty(q) ::= 우선순위큐 q가비어있는지를검사한다. is_full(q) ::= 우선순위큐 q가가득찼는가를검사한다. insert(q, x) ::= 우선순위큐 q에요소 x를추가한다. delete(q) ::= 우선순위큐로부터가장우선순위가높은요소를삭제하고이요 소를반환한다. find(q) ::= 우선순위가가장높은요소를반환한다.

5 우선순위큐 ADT 가장중요한연산은 insert 연산 ( 요소삽입 ), delete 연산 ( 요소삭제 ) 이다. 우선순위큐는 2 가지로구분 최소우선순위큐 최대우선순위큐

6 우선순위큐구현방법 배열을이용한우선순위큐 연결리스트를이용한우선순위큐 히프 (heap) 를이용한우선순위큐

7 우선순위큐구현방법 표현 방법 삽 입 삭 제 순서없는배열 O(1) O(n) 순서없는연결리스트 O(1) O(n) 정렬된배열 O(n) O(1) 정렬된연결리스트 O(n) O(1) 히프 O(logn) O(logn)

8 히프 (heap) 란? 히프란노드들이저장하고있는키들이다음과같은식을만족하는완전이진트리 최대히프 (max heap) 부모노드의키값이자식노드의키값보다크거나같은완전이진트리 key( 부모노드 ) key( 자식노드 ) 최소히프 (min heap) 부모노드의키값이자식노드의키값보다작거나같은완전이진트리 key( 부모노드 ) key( 자식노드 )

9 히프의높이 n 개의노드를가지고있는히프의높이는 O(logn) 히프는완전이진트리 마지막레벨 h 을제외하고는각레벨 i 에 2 i-1 개의노드존재 깊이노드의개수 1 1= = =

10 히프의구현방법 히프는배열을이용하여구현 완전이진트리이므로각노드에번호를붙일수있다 이번호를배열의인덱스라고생각 부모노드와자식노드를찾기가쉽다. 왼쪽자식의인덱스 = ( 부모의인덱스 )*2 오른쪽자식의인덱스 = ( 부모의인덱스 )*2 + 1 부모의인덱스 = ( 자식의인덱스 )/2

11 히프에서의삽입 히프에있어서삽입연산은회사에서신입사원이들어오면일단말단위치에앉힌다음에, 신입사원의능력을봐서위로승진시키는것과비숫 (1) 히프에새로운요소가들어오면, 일단새로운노드를히프의마지막노드에이어서삽입 (2) 삽입후에새로운노드를부모노드들과교환해서히프의성질을만족

12 upheap 연산 새로운키 k 의삽입연산후히프의성질이만족되지않을수있다 upheap 는삽입된노드로부터루트까지의경로에있는노드들을 k 와비교, 교환함으로써히프의성질을복원한다. 키 k 가부모노드보다작거나같으면 upheap 는종료한다 히프의높이가 O(logn) 이므로 upheap 연산은 O(logn) 이다.

13 upheap 알고리즘 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 PARENT(i);

14 HeapType 정의 #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;

15 삽입프로그램 // 현재요소의개수가 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 히프에서의삭제 최대히프에서의삭제는가장큰키값을가진노드를삭제하는것을의미 따라서루트노드가삭제된다. 삭제연산은회사에서사장의자리가비게되면먼저제일말단사원을사장자리로올린다음에, 능력에따라강등시키는것과비슷하다. (1) 루트노드를삭제한다 (2) 마지막노드를루트노드로이동한다. (1) 루트에서부터단말노드까지의경로에있는노드들을교환하여히프성질을만족시킨다.

17 downheap 알고리즘 히프의높이가 O(logn) 이므로 downheap 연산은 O(logn) 이다.

18 downheap 알고리즘 delete_max_heap(a) item A[1]; A[1] A[heap_size]; heap_size heap_size-1; i 2; // root의 left child, i 2*i 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 CHILD(largest); // i 2*i 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 전체프로그램 #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 전체프로그램 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(log(n)) 삭제도최악의경우, 가장아래레벨까지내려가야하므로역시트리의높이만큼의시간이걸린다. O(log(n))

23 히프정렬 히프를이용하면정렬가능 먼저정렬해야할 n 개의요소들을최대히프에삽입 한번에하나씩요소를히프에서삭제하여저장하면된다. 삭제되는요소들은값이증가되는순서 ( 최소히프의경우 ) 하나의요소를히프에삽입하거나삭제할때시간이 O(log(n)) 만큼 소요되고요소의개수가 n 개이므로전체적으로 O(n*log(n)) 시간이걸린다. ( 빠른편 ) 히프정렬이최대로유용한경우는전체자료를정렬하는것이아니라가장큰값몇개만필요할때이다. 이렇게히프를사용하는정렬알고리즘을히프정렬이라고한다.

24 히프정렬프로그램 // 우선순위큐인히프를이용한정렬 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);

25 이산이벤트시뮬레이션 이산이벤트시뮬레이션에서모든시간의진행은이벤트의발생에의해서 이루어진다. 우선순위큐를이용하여이벤트를저장하고이벤트의발생시각을 우선순위로하여이벤트를처리하는간단한시뮬레이션을작성하여보자.

26 이산이벤트시뮬레이션 #define ARRIVAL 1 #define ORDER 2 #define LEAVE 3 int free_seats=10; double profit=0.0; #define MAX_ELEMENT 100 typedef struct { int type; // 이벤트의종류 int key; // 이벤트가일어난시각 int number; // 고객의숫자 element; typedef struct { element heap[max_element]; int heap_size; HeapType;

27 이산이벤트시뮬레이션 // 초기화함수 void init(heaptype *h) { h->heap_size =0; // int is_empty(heaptype *h) { if( h->heap_size == 0 ) return TRUE; else return FALSE;

28 이산이벤트시뮬레이션 // 삽입함수 void insert_min_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; // 새로운노드를삽입

29 이산이벤트시뮬레이션 // 삭제함수 element delete_min_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;

30 이산이벤트시뮬레이션 // 0에서 n사이의정수난수생성함수 int random(int n) { return rand() % n; // 자리가가능하면빈자리수를사람수만큼감소시킨다. int is_seat_available(int number) { printf("%d명의고객도착 \n", number); if( free_seats >= number ){ free_seats -= number; return TRUE; else { printf(" 자리가없어서떠남 \n"); return FALSE;

31 이산이벤트시뮬레이션 // 주문을받으면순익을나타내는변수를증가시킨다. void order(int scoops) { printf(" 아이스크림 %d개주문받음 \n", scoops); profit += 0.35 * scoops; // 고객이떠나면빈자리수를증가시킨다. void leave(int number) { printf("%d명이매장을떠남 \n", number); free_seats += number;

32 이산이벤트시뮬레이션 // 이벤트를처리한다. void process_event(heaptype *heap, element e) { int i=0; element new_event; printf(" 현재시간 =%d\n", e.key); switch(e.type){ case ARRIVAL: // 자리가가능하면주문이벤트를만든다. if( is_seat_available(e.number) ){ new_event.type=order; new_event.key = e.key random(4); new_event.number=e.number; insert_min_heap(heap, new_event); break;

33 이산이벤트시뮬레이션 case ORDER: // 사람수만큼주문을받는다. for (i = 0; i < e.number; i++){ order(1 + random(3)); // 매장을떠나는이벤트를생성한다. new_event.type=leave; new_event.key = e.key random(10); new_event.number=e.number; insert_min_heap(heap, new_event); break; case LEAVE: // 고객이떠나면빈자리수를증가시킨다. leave(e.number); break;

34 int main() { element event; HeapType heap; unsigned int t = 0; init(&heap); // 처음에몇개의초기이벤트를생성시킨다. while (t < 5) { t += random(6); event.type = ARRIVAL; event.key = t; event.number = 1 + random(4); insert_min_heap(&heap, event); while (!is_empty(&heap)) { event = delete_min_heap(&heap); process_event(&heap, event); printf(" 전체순이익은 =%f입니다.\n ", profit);

35 이산이벤트시뮬레이션 현재시간 = 0 3 명의고객도착현재시간 = 1 4 명의고객도착현재시간 = 4 아이스크림 1 개주문받음아이스크림 3 개주문받음아이스크림 3 개주문받음현재시간 = 4 아이스크림 1 개주문받음아이스크림 1 개주문받음아이스크림 1 개주문받음아이스크림 2 개주문받음현재시간 = 4 2 명의고객도착현재시간 = 5 아이스크림 3 개주문받음아이스크림 2 개주문받음현재시간 = 6 4 명의고객도착자리가없어서떠남현재시간 = 6 4 명이매장을떠남현재시간 = 7 2 명이매장을떠남현재시간 = 10 3 명이매장을떠남전체순이익은 = 입니다.

36 허프만코드 이진트리는각글자의빈도가알려져있는메시지의내용을압축하는데사용될수있다. 이런종류의이진트리를허프만코딩트리라고부른다.

37 글자의빈도수 예를들어보자. 만약텍스트가 e, t, n, i, s 의 5 개의글자로만이루어졌다고가정하고각글자의빈도수가다음과같다고가정하자. 24

38 허프만코드생성절차

39 허프만코드프로그램 #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;

40 허프만코드프로그램 // 초기화함수 init(heaptype *h) { h->heap_size =0; // 삽입함수 void insert_min_heap(heaptype *h, element item) { // 프로그램 8.5 참조 // 삭제함수 element delete_min_heap(heaptype *h) { // 프로그램 8.5 참조

41 // 이진트리생성함수 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);

42 허프만코드프로그램 // 허프만코드생성함수 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);

43 허프만코드프로그램 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);

44 허프만코드프로그램 // 주함수 void main() { int freq[] = { 15, 12, 8, 6, 4 ; huffman_tree(freq, 5);