안녕하세요 c++ 공부하고있는 대학생입니다.
이번에는 저번에 max_heap 구성 한 것에 대한 heap sort에 대해 정리 해 보려고 합니다.
이전에 구성했던 코드에서 max_heap으로 구성한 그림입니다.
이진트리 특성상, 부모노드를 기준으로 왼쪽 자식노드부터 채워지기때문에, 인덱스를 보시면
root 노드인 9가 0번인덱스,
4가 1번인덱스,
7이 2번인덱스,
2가 3번인덱스,
3이 4번인덱스,
2가 5번인덱스,
2가 6번인덱스
이 순서대로 채워집니다.
heap sort의 원리는 다음과 같습니다.
- 비교해서 볼 노드는, 전체 노드의 개수에서 /2 (몫 연사자)를 한 값이다. (ex. 7개면, 3개만 보면된다.)
- 제일 마지막 노드와 root 노드를 비교해서 값이 마지막 노드가 크다면 swap한다.
- 마지막 노드의 부모노드와 비교해서 , 부모 노드가 크다면 swap한다.
처음에는 이렇게 9와 2를 바꾸어줍니다.
이러한 과정을 다 거치면..
이렇게 모두 바뀌게 됩니다.
우선 먼저 max_heap에 대한 소스코드입니다.
void heapify(node* root, int size) {
int i = size - 1;
do {
if (root[0].data < root[i].data) {
int temp = root[0].data;
root[0].data = root[i].data;
root[i].data = temp;
}
if (root[i].data > root[(i - 1) / 2].data) {
int temp = root[i].data;
root[i].data = root[(i - 1) / 2].data;
root[(i - 1) / 2].data = temp;
}
if (i <= (size - 1) / 2) {
if (root[i].data < root[(i + 1) * 2].data && root[(i + 1) * 2].right != NULL) {
int temp = root[i].data;
root[i].data = root[(i + 1) * 2].data;
root[(i + 1) * 2].data = temp;
}
if (root[i].data < root[(i * 2) + 1].data && root[(i * 2) + 1].left != NULL) {
int temp = root[i].data;
root[i].data = root[(i * 2) + 1].data;
root[(i * 2) + 1].data = temp;
}
}
i--;
} while (i != 0);
}그리고 heapsort에 대한 소스코드입니다.
void heapsort(node* root, int size) {
int i = size - 1;
int sizeNum = size - 1;
do {
int temp = root[0].data;
root[0].data = root[i].data;
root[i].data = temp;
root[i].left = NULL;
root[i].right = NULL;
if(i>1) heapify(root, i);
i--;
} while (i >= 0);
}do while 루프문을 통해서 비교할 노드 전체를 대상으로 접근하는 방식입니다.
완전히 swap된 노드는 더이상 비교 할 필요가 없기때문에, data값을 제외한 왼쪽 오른쪽 노드를 NULL값으로 끊어주기 위해 사용하였습니다.
if문을 통해 root노드가 아니라면, 비교 해 줄 필요가없기때문에 heapify 함수 호출을 통해 heapify 안에서 재귀문으로 조건에 맞춘 모습입니다.
이렇게해서 결과를 보여드리면,
inputdata는 제가 넣은 데이터이고, origin은 이진트리에 들어간 데이터입니다. 이진트리에서 제가 전위순회를 했기때문에, 9 2 4 7 3 2 2 순으로 출력되는것입니다.
heapify는 max_heap입니다. 출력을보면 max_heap이 형성된걸 볼 수 있습니다.
마지막으로 heapsort를 통해 2 2 2 3 4 7 9 로 출력됨을 볼 수 있습니다.
전체 소스코드를 올리며 정리를 마무리 하도록 하겠습니다.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 256
typedef struct node {
struct node* left;
struct node* right;
int data;
}node;
typedef struct tree {
struct tree* next;
int data;
}tree;
tree* root = NULL;
int size = 1;
tree* insert(tree* root, int data) {
if (root == NULL) {
root = (tree*)malloc(sizeof(tree));
root->next = NULL;
root->data = data;
size++;
return root;
}
else {
root->next = insert(root->next, data);
return root;
}
}
void print(node* root) {
if (root) {
printf("%d ", root->data);
print(root->left);
print(root->right);
}
}
void swap(int *a, int *b) {
int *temp = a;
a = b;
b = temp;
}
void heapify(node* root, int size) {
int i = size - 1;
do {
if (root[0].data < root[i].data) {
int temp = root[0].data;
root[0].data = root[i].data;
root[i].data = temp;
}
if (root[i].data > root[(i - 1) / 2].data) {
int temp = root[i].data;
root[i].data = root[(i - 1) / 2].data;
root[(i - 1) / 2].data = temp;
}
if (i <= (size - 1) / 2) {
if (root[i].data < root[(i + 1) * 2].data && root[(i + 1) * 2].right != NULL) {
int temp = root[i].data;
root[i].data = root[(i + 1) * 2].data;
root[(i + 1) * 2].data = temp;
}
if (root[i].data < root[(i * 2) + 1].data && root[(i * 2) + 1].left != NULL) {
int temp = root[i].data;
root[i].data = root[(i * 2) + 1].data;
root[(i * 2) + 1].data = temp;
}
}
i--;
} while (i != 0);
}
void heapsort(node* root, int size) {
int i = size - 1;
int sizeNum = size - 1;
do {
int temp = root[0].data;
root[0].data = root[i].data;
root[i].data = temp;
root[i].left = NULL;
root[i].right = NULL;
if(i>1) heapify(root, i);
i--;
} while (i >= 0);
}
int main() {
node binary[MAX_SIZE];
int size = 7;
printf("input data\n");
for (int i = 1; i <= size; i++) {
int key = 0;
scanf_s("%d", &key);
root = insert(root, key);
binary[i].data = root->data;
binary[i].left = NULL;
binary[i].right = NULL;
root = root->next;
if (i % 2 == 0) {
binary[i / 2].left = &binary[i];
}
else {
binary[i / 2].right = &binary[i];
}
}
printf("origin\n");
print(&binary[1]);
printf("\n");
printf("heapify result\n");
heapify(&binary[1], size);
print(&binary[1]);
printf("\n");
printf("heap result \n");
heapsort(&binary[1], size);
printf("\n");
for (int i = 1; i <= size; i++) {
printf("%d ", binary[i].data);
}
}heap sort를 구현하면서.. 되도록이면 직접 그림을 그려서 풀었습니다. 제가 자료구조를 공부할 때 주의깊게 보는점은..
- 의사코드를 작성하면서 어떻게 자료구조를 적용 할 지 고민한다.
- 그림을 그리면서 작성한 의사코드를 베이스로 잡는다.
- 소스코드로 구현하면서 구상대로 되었는지 확인한다.
이렇게 보면서 공부합니다.
그리고 실질적인 프로젝트를하면서 제가 c와 c++을 사용하면서 메모리에대한 벽에 자주 막히는 경우가 있습니다. 그때마다 잘 생각해보면, 자료구조로 어려움을 잘 빠져나왔었습니다.
자료구조가 항상 답은 아니지만, 공간복잡도 시간복잡도에 있어서 이득을 많이 주는 파트이기때문에, 더 열심히 공부하고 프로젝트의 상황에따라 어떤 자료구조를 사용 할 지, 생각 해 보는것도 중요하다고 생각합니다.
아직 미숙한 실력이지만 더욱 더 최적화되고 좋은 코드를 작성 할 수 있도록 노력하는것이 지금의 제가 하고있는 공부에서 가장 중요하게 생각하고있습니다. 그를 위해서는.. 컴구론, os도 공부를 열심히 해야한다고 생각합니다.
