[C언어로 쉽게 풀어쓴 자료구조] Chapter9. 우선순위 큐 (2)

9.6 머신 스레줄링

머신 스케줄링(machine schdling): 소요시간이 다른 여러 작업을 가장 최소의 시간으로 처리하는 것

- 머신 스케줄링에 대한 최적의 해를 찾는 방법 중 하나가 LPT이다.

LPT(longest processing time first): 가장 긴 작업을 우선적으로 스케줄에 할당하는 것.

가장 긴 작업인 빨강부터 초록까지 순차적으로 스케줄에 할당한 후

가장 먼저 끝나는 초록을 작업한 M3에 그 다음 작업인 보라를 할당한다.

 

- 항상 종료 시간이 최소인, 즉 작업이 가장 먼저 끝나는 기계가 다음 스케줄링에 선택된다.

- 작업을 할당한 후에는 기계의 종료 시간을 할당한 작업 시간만큼 증가시킨 후에 다시 최소 히프에 넣는다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200
#define SIZE 8

typedef struct{
	int id;
	int avail;
}element;

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

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

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

void insert_min_heap(HeapType *h, element item){
	int i;
	i = ++(h->heap_size);
	
	while((i != 1)&&(item.avail < h->heap[i/2].avail)){
		h->heap[i] = h->heap[i/2];
		i /=2;
	}
	h->heap[i] = item;
}

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].avail > h->heap[child+1].avail)){
			child ++;
		} 
		if(temp.avail < h->heap[child].avail) break; //최대 heap 만족하면 break
		
		h->heap[parent] =h->heap[child];
		parent = child;
		child *=2;
	}// whlie문을 빠져나오면 parent 위치가 확정됨
	h->heap[parent] = temp;
	return item;
}

#define JOBS 7
#define MACHINES 3

int main(){
	int jobs[JOBS]= {8,7,6,5,3,2,1};
	element m = {0,0};
	HeapType *h;
	h = create();
	init(h);
	
	for(int i=0;i<MACHINES;i++){
		m.id = i+1;
		m.avail=0;
		insert_min_heap(h,m);
	}
	
	for(int i=0;i<JOBS;i++){
		m = delete_min_heap(h);
		printf("JOB %d을 시간=%d부터 시간=%d까지 기계%d번에 할당\n",i,m.avail,m.avail+jobs[i]-1,m.id);
		m.avail += jobs[i];
		insert_min_heap(h,m);
	}
	return 0;
}

 

 

9.7 허프만 코드

● 허프만 코딩트리: 문자또는 글자의 빈도가 알려져 있을 때 메세지 또는 문자열을 압축시키기 위해

가변 길이의 코드를 만들어 사용하는 이진 트리

 

- 테이블은 문자와 빈도수를 데이터로 가진다.

- 빈도수가 높은 글자에 대해서는 짧은 비트열을 사용하고 빈도수가 낮으면 긴 비트열을 사용한다.

 

글자	빈도수
e	15
t	12
n	8
i	6
s	4

 

ex) 텍스트가 45글자이므로 한 글자당 3비트씩 사용하는 아스키 코드의 경우 45*3 = 135 비트가 필요

그러나 e, t, n은 2비트를, i,s는 3비트를 할당하면 15*2+12*2+8*2+6*3+4*3 = 88 비트로 표현가능

 

●  허프만 코드: 가변길이 코드를 해독하려면 모든 코드가 다른 코드의 첫부분이 아니여야 한다.

ex) 01000010이라는 코드에서 첫글자가 0인지 01인지 010인지를 파악하기 위해선

해석가능한 코드 테이블엔 0또는 01또는 010 셋 중 하나만 존재하여야 한다.

코딩된 비트열을 왼쪽에서 오른쪽으로 읽을 때 하나의 코드만 존재하는 코드를 만들기 위해 이진트리를 사용한다.

이러한 코드를 허프만 코드라고 한다.

 

허프만 코드 생성 절차

1. 빈도수에 따라 글자를 오름차순으로 나열 [s(4), i(6), n(8), t(12), e(15)]
2. 가장 작은 빈도수를 가지는 글자 2개를 단말노드로 하여 이진 트리를 구성
3. 두 단말노드의 부모노드인 루트의 값은 자식 노드의 값들을 합한 값 (4+6 =10)
4. 루트 노드를 다시 리스트에 삽입하면 [n(8),10, t(12), e(15)]가 된다.
5. 2번과 3번을 반복하여 새로운 트리를 구성한다. 이 때 새로운 노드는 (8+10=)18의 값을 가진다.

이 때 허프만 트리에서 왼쪽 간선은 비트1, 오른쪽 간선은 비트0을 나타낸다.

 

가장 작은 빈도수를 가지는 글자 2개를 얻기 위해서 최소 히프를 이용한다

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200

typedef struct TreeNode{
	int weight;
	char ch;
	struct TreeNode *left;
	struct TreeNode *right;
}TreeNode;

typedef struct{
	TreeNode *ptree;
	char ch;
	int key;
}element;

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

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

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

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

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; //최대 heap 만족하면 break
		
		h->heap[parent] =h->heap[child];
		parent = child;
		child *=2;
	}// whlie문을 빠져나오면 parent 위치가 확정됨
	h->heap[parent] = temp;
	return item;
}

TreeNode* make_tree(TreeNode *left, TreeNode *right){
	TreeNode *node = malloc(sizeof(TreeNode));
	node->left = left;
	node->right = right;
	return node;
}

TreeNode* destroy_tree(TreeNode *root){
	if(root == NULL) return;
	destroy_tree(root->left);
	destroy_tree(root->right);
	free(root);
}

int is_leaf(TreeNode* root){
	return !(root->left)&& !(root->right);
}

void print_array(int codes[],int n){
	for(int i=0; i<n;i++){
		printf("%d",codes[i]);
	}
	printf("\n");
}

void print_codes(TreeNode *root, int codes[],int top){
	if(root->left)
	{
		codes[top]=1;
		print_codes(root->left,codes,top+1);
	}
	if(root->right)
	{
		codes[top]=0;
		print_codes(root->right,codes,top+1);
	}
	if(is_leaf(root)){
		printf("%c: ",root->ch);
		print_array(codes,top);
	}
	
}

void huffman_tree(int freq[],char ch_list[],int n){
	TreeNode *node ,*x;
	//node는 문자와 빈도수 구조체를 최소 히프에 담기위한 노드
	//x는 최소값을 가지는 두 노드를 e1,e2에 저장해서 key를 합한 새로운 노드를 담기위한 노드
	HeapType *heap;
	element e,e1,e2;
	int codes[100];
	int top=0;
	
	heap=create();
	init(heap);
	for(int i=0;i<n;i++){
		node = make_tree(NULL,NULL);
		e.ch = node->ch = ch_list[i];
		e.key= node->weight = freq[i];
		e.ptree = node;
		insert_min_heap(heap,e);
	}
	for(int 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;
		printf("%d+%d->%d \n",e1.key,e2.key,e.key);
		insert_min_heap(heap,e);
	}
	e = delete_min_heap(heap);
	print_codes(e.ptree,codes,top);
	destroy_tree(e.ptree);
	free(heap);
}


int main(){
	char ch_list[]={'s','i','n','t','e'};
	int freq[] = {4, 6, 8, 12, 15};
	huffman_tree(freq,ch_list,5);
	return 0;
}