CHAP 8:우선순위큐

우선순위큐 우선순위큐(priority queue): 우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다.    자료구조    삭제되는 요소    스택    가장 최근에 들어온 데이터    큐    가장 먼저 들어온 데이터    우선순위큐    가장 우선순위가 높은  데이터 응용분야: 운영 체제에서의 작업 스케쥴링 네트워크 트래픽 제어 시뮬레이션 시스템

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

우선순위큐 구현방법 배열을 이용한 우선순위큐 연결리스트를 이용한 우선순위큐 Heap을 이용한 우선순위큐

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

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

Heap의 높이 n개의 노드를 가지고 있는 heap의 높이는 O(logn) Heap은 완전이진트리 마지막 레벨을 제외하고는 각 레벨 i에 2i개의 노드 존재 레벨 노드의 개수 0 1=20 1 2=21 2 4=22 3 3

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

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

upheap 연산 새로운 키 k의 삽입연산후 히프의 성질이 만족되지 않을 수 있다 키 k가 부모노드보다 작거나 같으면 upheap 연산은 종료된다. 힙의 높이가 O(logn)이므로 upheap연산은 O(logn)이다.

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);

삽입 프로그램 // 현재 요소의 개수가 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; // 새로운 노드를 삽입

힙에서의 삭제 최대힙에서의 삭제는 가장 큰 키값을 가진 노드를 삭제하는 것을 의미 -> 따라서 루트노드가 삭제된다. 루트노드를 삭제한다 마지막노드를 루트노드로 이동한다. 루트에서부터 단말노드까지의 경로에 있는 노드들을 교환하여 힙의 성질을 만족시킨다.

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

downheap 알고리즘 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[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); return 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;

삭제 프로그램 #include <stdio.h> #define MAX_ELEMENT 200 typedef struct { int key; } element; element heap[MAX_ELEMENT]; int heap_size; } HeapType; // 초기화 함수 init(HeapType *h) { h->heap_size =0; }

삭제 프로그램 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 >

힙의 복잡도 분석 삽입 연산에서 최악의 경우, 루트 노드까지 올라가야 하므로 트리의 높이에 해당하는 비교 연산 및 이동 연산이 필요하다. ->O(logn) 삭제도 최악의 경우, 가장 아래 레벨까지 내려가야 하므로 역시 트리의 높이 만큼의 시간이 걸린다. ->O(logn)

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

히프정렬 프로그램 // 힙정렬 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);

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

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

허프만 코드 생성 절차 우선순위큐에서 가장 작은 노드 2개를 꺼내고 그 합을 다시 큐에 삽입

허프만 코딩 트리 생성 #define MAX_ELEMENT 100 typedef struct TreeNode { int weight; struct TreeNode *left_child; struct TreeNode *right_child; } TreeNode; typedef struct { TreeNode *ptree; //각 element 당 관련된 tree node가 하나씩 존재, 그 node에 대한 포인터 int key; } element; element heap[MAX_ELEMENT]; int heap_size; } HeapType;

허프만 코딩 트리 생성 // 초기화 함수 init(HeapType *h) { h->heap_size =0; } // 삽입 함수 void insert_min_heap(HeapType *h, element item) // 프로그램 8.5 참조 // 삭제 함수 element delete_min_heap(HeapType *h)

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

허프만 코딩 트리 생성 // 허프만 코드 생성 함수 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); }

허프만 코딩 트리 생성 for(i=1;i<n;i++){ // 각 반복에서 2개 삭제후 1개 추가 (n-1번 반복) // 최소값을 가지는 두개의 노드를 삭제 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);

허프만 코딩 트리 생성 void main() { int freq[] = { 15, 12, 8, 6, 4 }; huffman_tree(freq, 5); }