우선순위 큐(Priority Queue)
- 컴퓨터에 우선순위의 개념이 필요할 때가 있음.
예) 네트워크 패킷 중에서 네트워크 관리와 관련된 패킷은 다른 일반 패킷보다 우선순위를 가짐.
예) 운영 시스템에서도 시스템 프로세스는 응용 프로세스보다 우선순위를 가지게 됨.
- 따라서 자료 구조에서도 이러한 우선순위를 지원하는 것이 필요함.
- 우선순위 큐(priority queue) : 우선순위의 개념을 큐에 도입한 자료 구조.
- 보통의 큐는 선입 선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 되지만, 우선순위 큐에서는 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 됨.
- 스택에 들어 있는 데이터들은 우선순위가 없음. 단지 먼저 들어간 데이터가 가장 늦게 나옴. (후입 선출(LIFO))
- 우선순위 큐와 스택 및 큐와의 비교
| 자료 구조 | 삭제되는 요소 |
| 스택 | 가장 최근에 들어온 데이터 |
| 큐 | 가장 먼저 들어온 데이터 |
| 우선순위 큐 | 가장 우선순위가 높은 데이터 |
- 우선순위 큐는 사실 가장 일반적인 큐라 할 수 있음.
-> 스택이나 큐도 우선순위 큐를 사용하여 얼마든지 구현할 수 있기 때문.
- 즉, 적절한 우선순위만 부여하면 우선순위 큐는 스택이나 큐로 동작할 것임.
- 우선순위 큐는 컴퓨터 여러 분야에서 이용됨.
예) 시뮬레이션 시스템(여기서의 우선순위는 대개 사건의 시각), 네트워크 트래픽 제어, 운영 체제에서의 작업 스케쥴링, 수치 해석적인 계산 등
- 우선순위 큐는 배열, 연결 리스트 등의 여러 가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 히프(heap).
- 우선순위 큐는 0개 이상의 요소의 모임임.
- 각 요소들은 우선순위 값을 가지고 있음.
- 가장 중요한 연산은 insert 연산(요소 삽입), delete 연산(요소 삭제).
- 우선순위 큐에서 요소들은 같은 우선순위를 가질 수 있음.
[우선순위 큐의 구현 방법]
- 우선순위 큐를 구현하는 방법은 여러 가지가 있는데 배열, 연결 리스트, 히프 등을 이용하는 방법이 있음.
(1) 배열을 사용하는 방법
1) 정렬이 안 된 배열
- 정렬이 안 된 배열을 사용하게 되면 삽입은 가장 간단함. (삽입의 시간 복잡도는 O(1))
- 삭제를 할 경우, 가장 우선순위가 높은 요소를 삭제하는 경우, 처음부터 끝까지 모든 요소들을 스캔하여야 함. (삭제의 시간 복잡도는 O(n))
그리고 요소가 삭제된 다음, 뒤에 있는 요소들을 앞으로 이동시켜야 하는 부담이 있음.
2) 정렬이 된 배열
- 정렬이 되어 있는 배열의 경우, 사입할 때 일일이 다른 요소와 비교하여 우선순위에 따라 삽입 위치를 결정해야 함.
- 삽입 위치를 찾기 위하여 순차 탐색이나 빠르게 찾기 위해서는 이진 탐색과 같은 방법을 이용할 수 있음.
- 삽입 위치를 찾은 다음에는 삽입 위치 뒤에 있는 요소들을 이동시켜서 빈자리를 만든 다음, 삽입해야 함. (삽입의 시간 복잡도는 O(n))
- 삭제시에는 간단함. 숫자가 높은 것이 우선순위가 높다고 가정하면 맨 뒤에 위치한 요소를 삭제하면 됨. (삭제의 시간 복잡도는 O(1))
(2) 연결 리스트를 사용하는 방법
- 연결 리스트를 이용하는 방법에도 배열의 경우와 크게 다르지 않음.
- 정렬된 상태로 연결 리스트를 유지할 수도 있고 정렬이 안 된 상태로 연결 리스트를 사용할 수 있음.
1) 정렬이 안 된 리스트
- 정렬이 안 된 리스트라면 삽입 시에는 첫 번째 노드로 삽입시키는 것이 유리함.
- 또한 삽입 시에 배열과 달리 다른 노드를 이동할 필요가 없음. (포인터만 변경하면 됨.)
- 따라서 삽입의 시간 복잡도는 O(1).
- 삭제 시에는 포인터를 따라서 모든 노드를 뒤져보아야 함. (삭제의 시간 복잡도는 O(n))
2) 정렬이 된 리스트
- 연결 리스트를 정렬시킨 상태로 사용한다면 우선순위가 높은 요소가 앞에 위치하는 것이 유리함.
- 따라서 우선순위가 높은 요소가 첫 번째 노드가 되도록 함.
- 삽입 시에는 우선순위 값을 기준으로 삽입 위치를 찾아야 하므로 시간 복잡도는 O(n).
- 삭제 시에는 첫 번째 노드를 삭제하면 되므로 시간 복잡도는 O(1).
(3) 히프를 사용하는 방법
- 히프(heap) : 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료 구조.
- 히프는 일종의 반정렬 상태를 유지함.
- 히프는 이러한 반정렬 상태를 이용하여 우선순위 큐를 구현함.
- 히프의 효율은 O(log₂n)으로서 다른 방법보다 상당히 유리함.
[히프]
- 컴퓨터 분야에서 히프는 완전 이진 트리(complete binary tree) 기반의 "더미"와 모습이 비슷한 특정 자료 구조를 의미함.
- 히프는 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조.
- 히프는 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말함.
- 즉 A가 B의 부모 노드라고 하고 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다고 하면, 다음과 같은 조건(히프 조건)이 항상 성립하는 트리.
key(A) ≥ key(B)
- 히프 트리에서는 중복된 값을 허용함에 유의해야 함.
- 이진 탐색 트리에서는 중복된 값을 허용하지 않았음.
- 히프 안에서 데이터들은 느슨한 정렬 상태를 유지함. (큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 정도)
- 히프의 목적은 삭제 연산이 수행될 때 마다 가장 큰 값을 찾아내기만 하면 되는 것이므로(가장 큰 값은 루트 노드에 있음.) 전체를 정렬할 필요는 없음.
- 히프에는 두 가지 종류의 히프 트리가 존재함.
-> 부등호만 달라지고 나머지는 완전히 동일함.
1) 최대 히프(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
key(부모 노드) ≥ key(자식 노드)
2) 최소 히프(min heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
key(부모 노드) ≤ key(자식 노드)
9
/ ＼
7 6
/ ＼ / ＼
5 4 3 2
/ ＼ /
2 1 3
(최대 히프)1
/ ＼
4 2
/ ＼ / ＼
7 5 3 3
/ ＼ /
7 8 9
(최소 히프)
- 히프는 완전 이진 트리이기 때문에 각각의 노드에 차례대로 번호를 붙일 수 있음.
- 따라서 히프를 저장하는 표준적인 자료 구조는 배열임.
- 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않음.
- 특정 위치의 노드 번호에는 새로운 노드가 추가되어도 변하지 않음에 유의.
예) 루트 노드의 오른쪽 노드의 번호는 항상 3번
- 배열을 이용하여 히프를 저장하면 완전 이진 트리에서처럼 자식 노드와 부모 노드를 쉽게 알 수 있음.
① 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
② 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
③ 부모의 인덱스 = (자식의 인덱스) / 2
9 1
/ ＼
7 2 6 3
/ ＼ / ＼
5 4 4 5 3 6 2 7
/ ＼ /
8 2 9 1 3 10
0 1 2 3 4 5 6 7 8 9 10 9 7 6 5 4 3 2 2 1 3
- 히프 트리 테스트 프로그램
// 히프 트리 테스트 프로그램
#include <stdio.h>
#define MAX_ELEMENT 200
typedef struct {
int key;
} element;
typedef struct {
element heap[MAX_ELEMENT];
int heap_size;
} HeapType;
// 초기화 함수
void init(HeapType *h) {
h->heap_size = 0;
}
// 현재 요소의 개수가 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[1 / 2].key)) {
h->heap[i] = h->heap[i / 2];
i /= 2;
}
h->heap[i] = 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;
}
// 주함수
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 > \n", e6.key);
}- 삽입 연산에서 새로운 요소 히프 트리를 타고 올라가면서 부모 노드들과 교환을 하게 되는데, 최악의 경우 루트 노드까지 올라가야 하므로 거의 트리의 높이에 해당하는 비교 연산 및 이동 연산이 필요함.
- 히프가 완전 이진 트리임을 생각하면 히프의 높이는 log₂n가 되므로 히프의 삽입 연산의 시간 복잡도는 O(log₂n)
- 삭제도 마찬가지로 마지막 노드를 루트로 가져온 후에 자식 노드들과 비교하여 교환하는 부분이 가장 시간이 걸리는 부분인데, 이 역시 최악의 경우 가장 아래 레벨까지 내려가야 하므로 역시 트리의 높이만큼의 시간이 걸림.
- 따라서 히프의 삭제 연산의 시간 복잡도는 O(log₂n)
[히프의 응용]
(1) 히프 정렬
- 최대 히프를 이용하면 정렬을 할 수 있음.
- n개의 요소는 O(nlog₂n) 시간 안에 정렬됨.
- 먼저 정렬해야 할 n개의 요소들로 최대 히프를 초기화하고 그 다음으로 한 번에 하나씩 요소를 히프에서 꺼내서 배열의 뒤부터 저장하면 됨.
- 삭제되는 요소들은 값이 감소되는 순서로 정렬되게 됨.
- 히트 트리의 전체 높이가 거의 log₂n이므로 (완전 이진 트리이므로) 하나의 요소를 히프에 삽입하거나 삭제할 때 히프를 재정비하는 시간이 log₂n 만큼 소요됨.
- 요소의 개수가 n개이므로 전체적으로 O(nlog₂n)의 시간이 걸림.
- 이 시간 복잡도는 삽입 정렬 같은 간단한 정렬 알고리즘이 O(n²) 걸리는 것에 비하면 좋은 편임.
- 또한 히프 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 몇 개만 필요할 때임.
- 이렇게 히프를 사용하는 정렬 알고리즘을 히프 정렬이라고 함.
- 히프 정렬 프로그램
// 히프 정렬 프로그램
#include <stdio.h>
#define MAX_ELEMENT 200
typedef struct {
int key;
} element;
typedef struct {
element heap[MAX_ELEMENT];
int heap_size;
} HeapType;
// 초기화 함수
void init(HeapType *h) {
h->heap_size = 0;
}
// 현재 요소의 개수가 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[1 / 2].key)) {
h->heap[i] = h->heap[i / 2];
i /= 2;
}
h->heap[i] = 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;
}
// 우선순위 큐인 히프를 이용한 정렬
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);
}
}
(2) 이산 이벤트 시뮬레이션
- 큐가 많이 사용되는 곳은 역시 시뮬레이션 분야.
- 컴퓨터 시뮬레이션은 실재하거나 이론적으로 존재하는 물리적인 시스템의 모델을 디자인하고 그 모델을 디지털 컴퓨터에서 실행하고 그 실행 결과를 분석하는 학문임.
- 시뮬레이션은 시간을 기반으로 해서 연속 시간(continuous time) 시뮬레이션, 이산 시간(discrete time) 시뮬레이션, 이산 이벤트(discrete event time) 시뮬레이션으로 나누어짐.
- 이산 이벤트 시뮬레이션에서 모든 시간의 진행은 이벤트의 발생에 의해서 이루어짐. (이벤트가 발생하면 시간이 진행됨.)
- 이산 이벤트 시뮬레이션에서는 많은 이벤트들이 발생하고 이 이벤트들은 시간적으로 먼저 발생된 이벤트가 먼저 처리되어야 함.
(3) 허프만 코드
- 이진 트리는 각 글자의 빈도가 알려져 있는 메시지의 내용을 압축하는 데 사용될 수 있음.
- 이런 특별한 종류의 이진 트리를 허프만 코딩 트리라고 부름.
예) 영문 신문에 실린 기사를 분석하여 각 글자들의 빈도수 분석
| A | 82 | - 테이블의 숫자는 빈도수(frequencies)라 불림. - 각 숫자들은 영문 텍스트에서 해당 글자가 나타나는 횟수. - 이 빈도수를 이용하여 데이터를 압축할 때는 각 글자들을 나타내는 최소 길이의 엔코딩 비트열을 만들 수 있음. - 데이터를 압축할 때는 우리가 흔히 사용하는 아스키(ASCII) 코드를 사용하지 않음. - 보통 전체 데이터의 양을 줄이기 위하여 고정된 길이를 사용하지 않고 가변 길이의 코드를 사용함. (각 글자의 빈도수에 따라서 가장 많이 등장하는 글자에는 짧은 비트열을 사용하고 잘 나오지 않는 글자에는 긴 비트열을 사용하여 전체의 크기를 줄이자는 것. 즉, 많이 등장하는 e를 나타내기 위하여 2비트를 사용하고 잘 나오지 않는 z를 나타내기 위하여 15비트를 사용하자는 것.) |
| B | 16 | |
| C | 32 | |
| D | 36 | |
| E | 123 | |
| F | 22 | |
| G | 26 | |
| H | 51 | |
| I | 71 | |
| ... | ||
| Z | 1 |
- 예를 들어, 만약 텍스트가 e, t, n, i, s의 5개의 5개의 글자로만 이루어졌다고 가정하고 각 글자의 빈도수가 다음과 같다고 가정.
| 글자 | 빈도수 |
| e | 15 |
| t | 12 |
| n | 8 |
| i | 6 |
| s | 4 |
- 텍스트의 길이가 45글자 이므로 한 글자를 3비트로 표시하는 아스키 코드의 경우, 45글자 * 3비트 = 135비트가 필요함.
- 하지만 만약 다음과 같이 가변 길이의 코드를 만들어서 사용했을 경우에는 더 적은 비트로 표현할 수 있음.
-> 15 * 2 + 12 * 2 + 8 * 2 + 6 * 3 + 4 * 3 = 88비트만 있으면 됨.
- 물론, 각각의 글자를 어떤 비트 코드로 표현했는지를 알려주는 테이블이 있어야 함.
| 글자 | 비트 코드 | 빈도수 | 비트 수 |
| e | 00 | 15 | 30 |
| t | 01 | 12 | 24 |
| n | 10 | 8 | 16 |
| i | 110 | 6 | 18 |
| s | 111 | 4 | 12 |
| 합계 | 88 |
- 글자를 나타내는 비트열은 서로 간에 혼동을 일으키지 않아야 함.
- 해결해야 될 문제
-> 압축해야 할 텍스트가 주어졌을 때 어떻게 그러한 비트 코드를 자동으로 생성할 것인지
-> 압축된 텍스트가 주어져 있을때 어떻게 복원할 것인지
- 해독하는 문제일 경우 만약 한 글자당 3비트가 할당된다면 메시지를 해독하는 것은 아주 쉬움. (메시지를 3비트씩 끊어서 읽으면 됨.)
- 만약 가변 길이 코드가 사용되었을 경우.
-> teen의 경우, 가변 코드를 사용하여 코딩하면 01000010이 됨.
-> 이 메시지를 어디서 끊어 읽어서 해독해야 하는가?
-> 첫 번째 글자의 경우, 하나의 테이블을 보면 0이나 010, 0100인 코드는 없기 때문에 첫 번째 글자는 01이 분명하고 01은 t임.
-> 또 다음 코드는 0, 00, 000, 0000 중의 하나임.
-> 그러나 같은 이유로 다음 코드는 00이 됨. 따라서 e가 됨.
-> 이런 식으로 계속 진행하면 teen이라고 하는 원문을 추출할 수 있음.
- 이러한 해독 과정을 가능하게 하는 원인은 코드를 관찰하여보면 모든 코드가 다른 코드의 첫 부분이 아니라는 것.
- 따라서 코딩된 비트열을 왼쪽에서 오른쪽으로 조사하여보면 정확히 하나의 코드만 일치하는 것을 알 수 있음.
- 이러한 특수한 코드를 만들기 위하여 이진 트리를 사용할 수 있음.
- 이런 종류의 코드를 허프만 코드(Huffman codes)라고 함.
- 허프만 코드를 만드는 절차
| 글자 | 빈도수 |
| e | 15 |
| t | 12 |
| n | 8 |
| i | 6 |
| s | 4 |
- 먼저 빈도수에 따라 5개의 글자를 나열하고(s(4), i(6), n(8), t(12), e(15)), 여기서 가장 작은 빈도수를 가지는 글자 2개(s(4), i(6))를 추출하여 이들을 단말 노드로 하여 이진 트리를 구성함.
- 루트의 값은 각 자식 노드의 값을 합한 값이 됨.
10
/ ＼
4 6 8 12 15
- 다시 글자들의 정렬된 리스트로 돌아가서 이 합쳐진 값을 글자들의 리스트에 삽입하여 (10, 8, 12, 15)를 얻음.
- 이 빈도수를 정렬하여 (8, 10, 12, 15)를 얻을 수 있고 다시 이 중에서 가장 작은 값 2개를 단말 노드로 하여 다음과 같은 이진 트리를 구성함.
18
/ ＼
/ ＼
10 ＼
/ ＼ ＼
4 6 8 12 15
- 다시 글자들의 정렬된 리스트로 돌아가서 이 합쳐진 값을 글자들의 리스트에 삽입하여 (12, 15, 18)을 얻음.
- 다시 이중에서 가장 작은 값 2개를 단말 노드로 하여 다음과 같은 이진 트리를 구성함.
18
/ ＼
/ ＼
10 ＼ 27
/ ＼ ＼ / ＼
4 6 8 12 15
- 같은 식으로 하여 (18, 27)이 되고 이 두 값을 단말 노드로 하여 이진 트리를 구성하면 다음과 같이 됨.
- 이 허프만 트리에서 왼쪽 간선은 비트 1을 나타내고 오른쪽 간선은 비트 0을 나타냄.
45
1 / ＼
18 ＼
/ ＼ ＼
1 / ＼ ＼ 0
10 ＼ 27
1 / ＼0 0＼ 1 / ＼ 0
4 6 8 12 15
- 이상과 같이 이진 트리를 구성하였으면 각 글자에 대한 허프만 코드는 단순히 루트 노드에서 단말 노드까지의 경로에 있는 간선의 라벨 값을 읽으면 됨.
- 즉 빈도수 6에 해당하는 글자인 i의 코드는 110이 됨.
- 같은 식으로 하여 다른 글자에 대한 허프만 코드 값을 얻을 수 있음.
- 허프만 코드 알고리즘에서 가장 작은 2개의 빈도수를 얻는 과정이 있음.
- 이것은 히프 트리를 이용하면 가장 효율적으로 구성될 수 있음. (여기서는 최소 히프를 이용해야 함.)
- 허프만 코드 프로그램(최소 히프 사용)
// 허프만 코드 프로그램(최소 히프 사용)
#include <stdio.h>
#include <stdlib.h>
#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;
// 초기화 함수
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;
// 한단계 아래로 이동
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));
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++) {
// 최솟값을 가지는 두 개의 노드를 삭제
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);
}
내용 출처 : C언어로 쉽게 풀어쓴 자료구조 (천인국 외 지음, 생능출판사)
'Computer Science > Data Structure' 카테고리의 다른 글
| [C] 탐색(Search) (0) | 2017.06.21 |
|---|---|
| [C] 해싱(Hashing) (0) | 2017.06.20 |
| [C] 그래프(Graph) (0) | 2017.06.19 |
| [C] 정렬(Sorting) (0) | 2017.06.18 |
| [C] 트리(Tree) (0) | 2017.06.01 |
| [C] 큐(Queue) (0) | 2017.05.23 |
| [C] 스택(Stack) (0) | 2017.05.11 |
| [C] 이중 연결 리스트(Doubly Linked List) (0) | 2017.05.06 |
