개념
보통의 큐는 FIFO(first-in-first-out) 원칙에 따라 먼저 들어온 데이터가 먼저 나간다. 그러나 우선순위 큐는 데이터들이 우선순위를 가진다. 따라서 우선순위가 높은 데이터가 먼저 나간다.
구현방법
- 배열 사용
- 연결리스트 사용
- 히프 사용
히프
히프는 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다.
완전 이진 트리이다.
히프의 종류는 최대히프, 최소히프 두 가지가 있다.
max heap : key(부모 노드) >= key(자식 노드)
min heap : key(부모 노드) <= key(자식 노드)
허프만 코드
각 글자의 빈도수를 파악할 수 있다.
이 빈도수를 활용하여 데이터를 압축할 수 있다. ->영상압축, 딥러닝 등에 활용
//최소히프를 사용한 허프만 코드
#include<stdio.h>
#include<stdlib.h>
#define MAX_ELEMENT 200
typedef struct TreeNode {
int weight;
char ch;
struct TreeNode *left;
struct TrreeNode *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;
}
//현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다.
//삽입 함수
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;
//한 단계 아래로 이동
h->heap[parent] = h->heap[child];
parent = child;
child *= 2;
}
h->heap[parent] = temp;
return item;
}
//이진 트리 생성 함수
TreeNode * make_tree(TreeNode * left, TreeNode * right)
{
TreeNode * node = (TreeNode*)malloc(sizeof(TreeNode));
node->left = left;
node->right = right;
return node;
}
//이진 트리 제거 함수
void 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)
{
//1을 저장하고 순환호출한다.
if(root->left){
codes[top] = 1;
print_codes(root->left, codes, top+1);
}
//0을 저장하고 순환호출한다.
if(root->left){
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)
{
int i;
TreeNode *node, *x;
HeapType *heap;
element e, e1, e2;
int codes[100];
int top = 0;
heap = create();
init(heap);
for(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(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(void)
{
char ch_list[] = {'s', 'i', 'n', 't', 'e'};
int freq[] = {4,6,8,12,15};
huffman_tree(freq, ch_list, 5);
return 0;
}
결과
댓글