2021.05.19 - [전체글] - 자료구조 공부 #18 (트리연산)
우선순위 큐
- 우선순위를 가진 항목들을 저장하는 큐
- 선입선출 순서가 아니라 우선순위가 높은 데이터가 먼저 나가게 설계됨
- 스택이나 선입선출 큐를 우선순위 큐로 구현 할수 있음
| 자료구조 | 삭제되는요소 |
| 스택 | 가장 최근에 들어온 요소 |
| 큐 | 가장 먼저 들어온 요소 |
| 우선순위 큐 | 가장 우선순위가 높은 데이터 |
- 응용분야
- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영 체제에서 작업 스케줄링
우선순위 큐 구조(ADT)
- 가장 중요한 연산은 insert 연산, delete연산이다
- 우선순위 큐는 2가지로 구분
- 최소 우선순위 큐
- 최대 우선순위 큐
우선순위 큐 구현 방법
- 배열을 이용한 우선순위 큐
- 연결 리스트를 이용한 우선순위 큐
- 힙(heap)을 이용한 우선순위 큐
- 완전 이진트리 모양으로 구현하는것
힙(heap) : 자료구조에선 완전 이진 트리의 개념
- 추후 운영체제 에선 메모리공간의 한 공간 개념(스택과 전역 사이에 존재하는 빈 공간)
- c에선 malloc(동적할당) 함수와 연관이 있다
표현 방법에 따른 삽입, 삭제 시간복잡도
| 표현방법 | 삽입 | 삭제 |
| 순서없는 배열 | O(1) | O(n) |
| 순서없는 연결 리스트 | O(1) | O(n) |
| 정렬된 배열 | O(n) | O(1) |
| 정렬된 연결리스트 | O(n) | O(1) |
| 힙(heap) | O(log n) | O(log n) |
우선순위 큐를 힙(heap)으로 구현하는 이유
배열로 구현하는 경우에는 삽입 삭제 연산에 경우 O(1), O(n) 정렬된 경우엔, O(n), O(1) 이다.
리스트로 구현하는 경우에는 삽입 삭제 연산에 경우 O(1), O(n), 정렬된 경우엔 O(n), O(1)이다.
반대로 힙에 경우에는 O(log n), O(log n) 으로 일정해서 시간 복잡도의 편차가 큰 배열 과 리스트로 구현하는 것 보다, 힙으로 구현 하는 것이 좋다.
2021.03.09 - [이론공부/자료구조] - 자료구조 공부#3 (알고리즘의 성능 분석)
시간 복잡도 관련 내용
힙(heap)
- 노드의 키들이 다음 식을 만족하는 완전 이진트리
- key(부모 노드) ≥ key(자식 노드)
최대 힙(max heap)
부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진트리
key(부모노드) ≥ key(자식 노드)
최소 힙(min heap)
부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진트리
key(부모노드) ≤ key(자식노드)
힙의 높이
- n개의 노드를 가지고 있는 힙의 높이는 O(log2 n)
- 힙은 완전 이진트리
- 마지막 레벨 h는 제외하고는 각 레벨 i에 2^i+1개 노드 존재
힙을 배열로 이용하여 구현
- 완전 이진트리므로 각 노드에 번호를 붙일 수 있다.
- 이 번호를 배열에 인덱스로 해서 구현
중간 삽입에 경우 배열을 재배치 하기위해 복잡해 질 수 있음
- 부모 노드와 자식 노드를 찾기 쉬움
- 왼쪽 자식의 인덱스 = (부모의 인덱스)*2
- 오른쪽 자식의 인덱스 = (부모의 인덱스)*2+1
- 부모의 인덱스 = (자식의 인덱스)/2
#define MAX_ELEMENT 200
typedef struct{
int key;
}element;
typedef struct{
element heap[MAX_ELEMENT];
int heap size;
}HeapType;
HeapType heap; //정적메모리할당
HeapType* heap = creat(); //동적메모리할당
힙에서의 삽입
힙에서 삭제
힙(heap) C++ 구현
#define MAX_ELEMENT 200
typedef struct {
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_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; // 새로운 노드를 삽입
}
// 삭제 함수
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 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;
}배열을 이용해서 구현되었다.
힙의 복잡도 분석
- 삽입 연산에서 최악의 경우, 루트 노드까지 올라갸야 하므로, 트리의 높이에 해당하는 비교 연산, 이동연산이 필요함
- -> O(log n)
- 삭제도 최악의 경우, 가장 아래 레벨까지 내려가야 함, 트리의 높이 만큼의 시간이 걸림
- -> O(log n)
힙 정렬
- 힙을 이용하면 정렬 가능
- 먼저 정렬해야 할 n개의 요소들을 최대 힙에 삽입
- 한번에 하나씩 요소를 힙에서 삭제하여 저장하면 된다
- 삭제되는 요소들은 값이 증가되는 순서(최소힙의 경우)
- 하나의 요소를 힙에 삽입하거나, 삭제할 때 시간이 O(log n) 만큼 소요되고, 요소의 개수가 n개 이므로 전체적으로 O(log n)의 시간이 걸림
- 힙 정렬이 최대로 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만이 필요할 때이다.
- 이렇게 힙을 사용하는 정렬 알고리즘을 힙 정렬이라고 한다.
void heap_sort(element a[], int n){
int i;
HeapType* h;
h=create();
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);
}
free(h);
}
#define SIZE 8
int main(void){
element list[SIZE] = {23, 56, 11, 9, 56, 99, 27, 34};
heap_sort(list,SIZE);
for (int i =0; i<SIZE; i++){
prinf("%d", list[i].key);
}
printf("\n");
return 0;
}
머신 스케줄링
어느 작업을 어느 기계에 할당을 해줘야 하는경우에 힙이 사용된다.
LPT 방법
C++로 구현
#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200
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;
// 현한 단계 아래로 이동
h->heap[parent] = h->heap[child];
parent = child;
child *= 2;
}
h->heap[parent] = temp;
return item;
}
#define JOBS 7
#define MACHINES 3
int main(void) {
int jobs[JOBS] = { 8, 7, 6, 5, 3, 2, 1 }; // 작업은 정렬되어 있다고 가정
element m = { 0, 0 };
HeapType* h;
h = create();
init(h);
// 여기서 avail 값은 기계가 사용 가능하게 되는 시간이다.
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;
}
허프만 코드
- 이진 트리는 각 글자의 빈도가 알려져 있는 메시지의 내용을 압축하는데 사용될 수 있다.
- 이런 종류의 이진 트리를 허프만 코딩 트리라고 한다.
글자의 빈도수
- 예를 들어, 텍스트가 e, t, n, i, s의 5글자로 이루어 졌을때, 각 글자의 빈도수가 다음과 같다고 가정하자
코드 생성 절차
#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;
}
// 현재 요소의 개수가 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->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) {
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;
}
우선순위큐, 그것을 구현하기 편하게 해주는 힙, 힙을 이용해 구현할 수 있는 다양한 알고리즘을 이해하자
'이론공부 > 자료구조' 카테고리의 다른 글
| 자료구조 공부 #21 (그래프2) (0) | 2021.06.14 |
|---|---|
| 자료구조 공부 #20 (그래프) (0) | 2021.06.08 |
| 자료구조 공부 #18 (트리연산) (0) | 2021.05.19 |
| 자료구조 공부 #17 (트리순회) (0) | 2021.05.16 |
| 자료구조 공부 #16 (트리) (0) | 2021.05.04 |
