이번에는 힙의 정의와 우선 순위 큐에 대해서 알아보겠습니다.
기본 개념을 아시는 분은 아래 최대 힙 트리 구현로 바로 가주시면 됩니다.
(완전 이진 트리 : 트리의 왼쪽 노드부터 차곡차곡 쌓이는 트리)
1. 최대 트리와 최대 힙
최대 트리 : 트리의 모든 노드에 대해 부모 노드의 데이터 값이 자식 노드의 데이터 값보다 크거나 같습니다.
부모 노드의 데이터 값 >= 자식 노드의 데이터 값
최대 힙 : 최대 트리면서 완전 이진 트리 입니다.
2. 최소 트리와 최소 힙
최소 트리 : 트리의 모든 노드에 대해 부모 노드의 데이터 값이 자식 노드의 데이터 값보다 작거나 같습니다.
부모 노드의 데이터 값 <= 자식 노드의 데이터 값
최소 힙 : 최소 트리면서 완전 이진 트리 입니다.
3. 우선 순위 큐
선입선출 (예: 일반적인 큐)이 아니라 우선 순위의 순서대로 삭제 되는 큐
3-1. 우선 순위 큐의 구현 방법 비교
3-2. 우선 순위 큐의 예
비행기 탑승 대기, OS의 작업 스케줄링 등
최대 힙 트리 구현
최대 힙이 우선 순위 큐와 동일한 원리를 가집니다.
따라서 해당 게시물에선 최대 힙만 구현해보도록 하겠습니다.
최대 힙의 특징은 다음과 같습니다.
여기서 부터 (트리 == 최대 힙 트리)입니다.
1. 항상 부모 노드가 자식 노드 보다 같거나 크다.
* 형제 노드끼리의 크기는 전혀 상관이 없다.
2. 트리에 노드를 삽입할 때는 항상 마지막 노드에 추가하고 해당 노드의 부모 노드와 비교하며 위치를 바꿔줍니다.
3. 트리에 노드를 삭제할 때는 항상 가장 처음 노드 (root 노드)부터 삭제합니다. (우선 순위 큐)
구현 하는 방법은 다른 알고리즘에 비해 굉장히 간단합니다.
1. 최대 힙 트리의 ADT
void Input_Data(Heap *hp, int data): 트리에 노드를 추가합니다.
void Delete_Data(Heap *hp): 트리에서 노드를 제거합니다.
void Print_Heap(Heap *hp): 트리의 노드를 출력합니다.
가장 큰 특징은 Delete_Data 함수에서 따로 특정 노드를 삭제하지 않기 때문에 data 인자를 받아오지 않아도 됩니다.
내부 알고리즘이 일반적인 제거 함수와 조금 다르긴 한데 다음 목차에 코드와 함께 알아보겠습니다.
2. 최대 힙 트리 구현
2-1. 구조체 선언
typedef struct NODE{
int data;
} Node;
typedef struct HEAP{
Node heap[100]; // 저장할 힙 트리의 노드 갯수를 정해줍니다.
int size; // 구조체 배열로 트리를 구성할 때 필요한 변수입니다.
} Heap;
2-2. 노드 추가
완전 이진 트리이기 때문에 새로운 노드는 항상 가장 왼쪽의 노드부터 채워집니다.
이때 해당 노드는 부모 노드와 크기가 비교되어 위치를 바꿔나갑니다. (새로 들어온 노드가 부모 노드 보다 클 때)
만약 새로 들어온 노드가 기존 트리의 노드 중에 가장 큰 데이터 값을 가지고 있다면 root 노드 자리까지 계속 데이터를 교환하며 올라갑니다.
void Input_Data(Heap *hp, int data){ // 노드와 함께 데이터를 추가합니다.
int i = 0; // 외부에서 선언된 hp는 포인터가 아니기 때문에 Input_Data(&hp, 3)과 같이 넣어줘야합니다.
int tmp; // SWAP을 실시할 때 사용됩니다.
hp->size++; // 노드를 추가할 때 size를 1 증가시킵니다.
i = hp->size; // 편의를 위해 size를 i 변수에 저장합니다.
hp->heap[i].data = data; // i 번째 노드에 데이터를 저장합니다.
while(i > 1){ // root 노드가 아닐 때는 새로 들어온 노드와 부모 노드와 크기를 비교해야 합니다.
if(hp->heap[i/2].data < hp->heap[i].data){ // i의 부모 노드는 i/2입니다.
tmp = hp->heap[i].data; // 부모 노드 보다 새로운 노드의 데이터가 크면 두 노드의 데이터를 교환해줍니다.
hp->heap[i].data = hp->heap[i/2].data;
hp->heap[i/2].data = tmp;
i = i/2; // 새로운 노드는 i/2 번째에 저장되어 있으므로,
// 다시 새롭게 들어간 자리의 부모 노드와 크기 교환 비교를 위해 i를 i/2로 갱신해준다.
}
else{ // 새로 들어온 노드가 부모 노드 보다 크기가 작거나 같으면 반복문을 정지합니다.
break;
}
}
}
2-3. 노드 삭제
노드를 삭제할 때는 가장 마지막 노드의 값을 가장 처음 노드에 저장하고 자식 노드와 크기를 비교하며 위치를 교환해 나갑니다.
루트 노드에 마지막 노드의 데이터가 저장되고, 크기 비교는 입력과 정반대라고 생각하시면 편합니다.
void Delete_Data(Heap *hp){ // root 노드를 삭제합니다.
int i = 1; // 항상 가장 처음 노드를 출력하기 때문에 i를 1로 설정합니다.
int j = 0;
int tmp;
hp->heap[i].data = hp->heap[hp->size--].data; // 가장 처음 노드에 마지막 노드의 데이터를 저장한 뒤, 사이즈를 하나 줄여줍니다.
while(i <= hp->size){ // i는 조건문 내부에서 계속 갱신됩니다. (바뀐 위치의 노드 인덱스로)
j = 2*i; // i번째 노드의 자식 노드는 2*i와 2*i+1번째 노드입니다.
if(j > hp->size){ // j는 자식 노드 인덱스이기 때문에 노드의 총 갯수보다 클 수 없습니다.
break;
}
if(hp->heap[i].data >= hp->heap[j].data && hp->heap[i].data >= hp->heap[j+1].data){
break; // 부모 노드의 데이터 값이 자식 노드 보다 크다면 조건문을 종료합니다.
}
if(hp->heap[j].data < hp->heap[j+1].data){
j = j+1; // 두 자식 노드 중에 큰 노드가 새로운 부모 노드가 되어야 합니다.
}
tmp = hp->heap[j].data; // 삭제된 자리에 자식 노드 중 큰 자식 노드의 데이터가 저장됩니다.
hp->heap[j].data = hp->heap[i].data;
hp->heap[i].data = tmp;
i = j; // 바뀐 위치의 인덱스로 i를 갱신합니다. (이때 항상 j 번째에 트리의 가장 마지막 노드 데이터가 저장되어 있습니다.)
}
}
2-4. 노드 출력
출력은 최대 힙 트리가 완전 이진 트리이기 때문에 2의 제곱 수대로 노드 데이터를 출력하면 깔끔하게 나옵니다.
void Print_Heap(Heap *hp){
int i = 1;
int k = 1;
while (i <= hp->size){
for(int j = 1; j <= pow(2, k-1); j++){ // poe(a, b)는 a^(b)와 동일합니다.
if(i > hp->size){
break;
}
printf("%2d ", hp->heap[i].data);
i++;
}
printf("\n");
k++;
}
}
3. 최대 힙 트리의 전체 코드 및 출력 결과
항상 전체 코드엔 확인을 위한 출력부와 주석이 포함되어 있습니다.
3-1. 전체 코드
#include <stdio.h>
#include <stdlib.h>
/*--------구조체 선언--------*/
typedef struct NODE{
int data;
} Node;
typedef struct HEAP{
Node heap[100];
int size;
} Heap;
/*------------------------*/
/*----------함수 선언--------*/
void Input_Data(Heap *hp, int data);
void Delete_Data(Heap *hp);
void Print_Heap(Heap *hp);
/*------------------------*/
int main(int argc, const char * argv[]) {
Heap hp;
Input_Data(&hp, 31);
Input_Data(&hp, 8);
Input_Data(&hp, 30);
Input_Data(&hp, 14);
Input_Data(&hp, 24);
Input_Data(&hp, 2);
Input_Data(&hp, 5);
Input_Data(&hp, 3);
Print_Heap(&hp);
Delete_Data(&hp);
Print_Heap(&hp);
Delete_Data(&hp);
Print_Heap(&hp);
Delete_Data(&hp);
Print_Heap(&hp);
return 0;
}
void Input_Data(Heap *hp, int data){
int i = 0;
int tmp;
hp->size++;
i = hp->size;
hp->heap[i].data = data;
puts("\nInputing data starts.");
while(i > 1){
if(hp->heap[i/2].data < hp->heap[i].data){
tmp = hp->heap[i].data;
hp->heap[i].data = hp->heap[i/2].data;
hp->heap[i/2].data = tmp;
i = i/2;
}
else{
break;
}
}
printf("hp->heap[%d].data = %d.\n", i, hp->heap[i].data);
puts("Inputing data is complete.");
}
void Delete_Data(Heap *hp){
int tmp;
int i = 1;
int j = 0;
hp->heap[i].data = hp->heap[hp->size--].data;
while(i <= hp->size){
j = 2*i;
if(j > hp->size){
break;
}
if(hp->heap[i].data >= hp->heap[j].data && hp->heap[i].data >= hp->heap[j+1].data){
break;
}
if(hp->heap[j].data < hp->heap[j+1].data){
j = j+1;
}
tmp = hp->heap[j].data;
hp->heap[j].data = hp->heap[i].data;
hp->heap[i].data = tmp;
i = j;
}
}
void Print_Heap(Heap *hp){
int i = 1;
int k = 1;
puts("\nPrinting starts.");
while (i <= hp->size){
for(int j = 1; j <= pow(2, k-1); j++){
if(i > hp->size){
break;
}
printf("%2d ", hp->heap[i].data);
i++;
}
printf("\n");
k++;
}
puts("Printing is complete.");
}
3-2. 출력 결과
데이터를 크기에 상관없이 입력한 결과입니다.
무작위로 넣은 데이터는 다음과 같이 크기 순서대로 정렬되어 트리에 저장됩니다.
노드 삭제 시 가장 윗 노드에 저장된 데이터 부터 차례로 빠져나가는 것을 아래 그림을 통해 확인 할 수 있습니다.
계속해서 트리는 완전 이진 트리 형태를 유지합니다.
'Programming > C' 카테고리의 다른 글
| [자료구조 C 언어] C 프로그래밍 자료구조 - 15 : 그래프(1) 기본 개념 (0) | 2020.03.18 |
|---|---|
| [자료구조 C 언어] C 프로그래밍 자료구조 - 14 : 이진 탐색 트리 (Binary Search Tree) (0) | 2020.03.18 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 12 : 스레드 이진 트리 (Thread Binary Tree) (0) | 2020.03.16 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 11 : 트리, 이진 트리의 개념 (Tree, Binary Tree) (0) | 2020.03.11 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 10 : 이중 연결리스트 (Doubly Linked List) (0) | 2020.03.10 |