max_heap 구성하기

안녕하세요 c++ 공부하고있는 대학생입니다.

이번에는 heap정렬을 들어가기 전, max_heap 구성하는 방법에 대해서 정리하고자 합니다.

이진트리까지는 저번에 올렸던것과 동일하며, 핵심부분인 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) {

				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) {
				int temp = root[i].data;
				root[i].data = root[(i * 2) + 1].data;
				root[(i * 2) + 1].data = temp;
			}
		}
		i--;
	} while (i != 0);
	print(&root[0]);
}

이렇게 구성되어있습니다.
완전 이진트리구조이어서, 왼쪽부터 오른쪽순으로 순차대로 데이터가 들어가는 구조입니다.
힙 구조를 만들기 위해서는,

1. 노드의 총 개수의 1/2 개의 노드를 기준으로 비교하면 된다.
2. root노드는 0번이며, 부모노드는 (i-1)/2이다.

제가 구성한 코드는 이렇게 되어있습니다. 그래서 do while문의 조건의 경우, i = 노드의 총 개수 로 선언 한 다음에, i !=0 으로 모두 체크하는 코드입니다.

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) {

				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) {
				int temp = root[i].data;
				root[i].data = root[(i * 2) + 1].data;
				root[(i * 2) + 1].data = temp;
			}
		}
		i--;
	} while (i != 0);

이렇게 do while문을 다 실행하면 힙구조에서 최대 힙 구조를 만들 수 있습니다.

결과를 보여드리고 마무리 해 보도록 하겠습니다.

전체 소스코드.

#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) {

				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) {
				int temp = root[i].data;
				root[i].data = root[(i * 2) + 1].data;
				root[(i * 2) + 1].data = temp;
			}
		}
		i--;
	} while (i != 0);
	print(&root[0]);
}

int main() {
	node binary[MAX_SIZE];
	printf("size input : ");
	int size = 0;
    scanf_s("%d",&size);
	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");
	heapify(&binary[1], size);

	//printf("heapify\n");
	//print(&binary[1]);
}