자료구조(12) - 힙의 ADT와 구현

#include <stdio.h>
#include <stdlib.h>

/*
자료 : 정수
기능1 삽입 : 원소를 Max 힙에 삽입한다.
기능2 삭제 : 원소를 Max 힙에서 삭제한다.
기능3 조회 : Max 힙에서 최대값을 조회한다.
기능4 순회 : Heap의 모든 원소를 level-order로 순회한다.
*/

typedef int* Heap; //typedef를 통한 변환

int left_child(const int index) {
	return 2 * index + 1;
}

int right_child(const int index) {
	return 2 * index + 2;
}

int parent(const int index) {
	return (index - 1) / 2;
}

//+ empty한지 확인
int is_empty(const int num_of_nodes) {
	if (num_of_nodes == 0) {
		return 1; //비었으면 참
	}
	else {
		return 0;//아니면 거짓
	}
}

void swap(int* x, int* y) {
	int temp = *x;
	*x = *y;
	*y = temp;

	return; // swap용 함수
}

//+ leaf node인지 확인
int is_leaf(const int index, const int num_of_nodes) {
	if (left_child(index) > num_of_nodes - 1) {
		// 마지막 노드의 index는 num_of_nodes -1이니까
		return 1;
	}
	else {
		return 0;
	}
}

//+ root node인지 확인
int is_root(const int index) {
	if (index == 0) {
		return 1;
	}
	else {
		return 0;
	}
}

// +) 핵심 기능, insertion Heapify
int insertion_heapify(Heap st, const int index) {
	if (is_root(index) || st[index] < st[parent(index)]) {
		return 1; // 탈출 조건 및 성공하면 1 반환
	}
	else {
		swap(&st[index], &st[parent(index)]);
		return insertion_heapify(st, parent(index));
	}

	return -1;// 실패하면 -1 반환
}

//기능1 삽입
int insert(Heap* st, const int value, int* num_of_nodes) {
	if (is_empty(*num_of_nodes)) {
		*st = (Heap)malloc(sizeof(int) * (*num_of_nodes + 1));
	}//원소가 없으면 할당
	else {
		Heap new_st = (Heap)realloc(*st, sizeof(int) * (*num_of_nodes + 1));
		*st = new_st;
	}//재할당

	(*st)[*num_of_nodes] = value;
	// 이중 포인터를 이용한 배열 접근을 이렇게 쓸 수도 있다.

	printf("%d is pushed into Heap!\n\n", value);
	*num_of_nodes += 1;
	//대입
	//num_of_nodes 증가

	insertion_heapify(*st, *num_of_nodes - 1);
	// 마지막 노드의 인덱스는 num_of_nodes -1

	return 0;
}

// +) 핵심 기능, deletion_heapify
int deletion_heapify(Heap st, const int index, const int num_of_nodes) {
	if (is_leaf(index, num_of_nodes)) {
		// 탈출 조건1 : 자식이 없을 때
		return 1;
	}
	else if (right_child(index) > num_of_nodes - 1) {
		//자식이 하나 있을 때

		int l_index = left_child(index);

		if (st[index] >= st[l_index]) {
			// 탈출 조건2 : 왼쪽 자식보다 크거나 같을 때
			return 1;
		}
		else {
			swap(&st[index], &st[l_index]);
			return deletion_heapify(st, l_index, num_of_nodes);
		}
	}
	else {
		// 자식이 둘 다 있을 때

		int l_index = left_child(index);
		int r_index = right_child(index);

		if (st[index] >= st[l_index] && st[index] >= st[r_index]) {
			// 탈출 조건3 : 두 자식보다 크거나 같을 때
			return 1;
		}
		else if (st[index] >= st[l_index] && st[index] < st[r_index]) {
			// 오른쪽 자식이 더 크면
			swap(&st[index], &st[l_index]);
			return deletion_heapify(st, l_index, num_of_nodes);
		}
		else if (st[index] >= st[r_index] && st[index] < st[l_index]) {
			// 왼쪽 자식이 더 크면
			swap(&st[index], &st[r_index]);
			return deletion_heapify(st, r_index, num_of_nodes);
		}
		else {
			// 두 자식 모두 다 부모보다 크면

			if (st[l_index] > st[r_index]) {
				// 왼쪽 자식이 오른쪽 자식보다 크면
				swap(&st[index], &st[l_index]);
				return deletion_heapify(st, l_index, num_of_nodes);
			}
			else {
				// 오른쪽 자식이 왼쪽 자식보다 크면
				swap(&st[index], &st[r_index]);
				return deletion_heapify(st, r_index, num_of_nodes);
			}
		}
	}


	return -1;// 실패하면 -1 반환
}


//기능2 제거
int Delete(Heap* st, int* num_of_nodes) {
	if (is_empty(*num_of_nodes)) {
		printf("Heap is empty!\n\n");
		return -1;
	}//원소가 없으면 오류

	int ret = **st;// ret값을 미리 저장(재할당을 위해)

	(*st)[0] = (*st)[*num_of_nodes - 1];
	// 루트에 마지막 값을 대입한다.
	// 이중 포인터를 이용한 배열 접근을 이렇게 쓸 수도 있다.

	*num_of_nodes -= 1;// num_of_nodes 감소
	deletion_heapify(*st, 0, *num_of_nodes);

	if (*num_of_nodes == 0) {
		*st = NULL;
	}//비었으면 NULL
	else {
		Heap new_st = (Heap)realloc(*st, sizeof(int) * (*num_of_nodes));
		*st = new_st;
	}//아니면 재할당

	return ret;// Delete한 원소 리턴
}

//기능3 조회
int search(Heap st, const int num_of_nodes) {
	if (is_empty(num_of_nodes)) {
		printf("Heap is empty!\n\n");
		return -1;
	}//원소가 없으면 오류

	return st[0];
}

//기능4 순회(Level_order_traversal)
int level_order_traversal(Heap st, const int num_of_nodes) {
	if (is_empty(num_of_nodes)) {
		printf("Heap is empty!\n\n");
		return -1;
	}//원소가 없으면 오류

	for (int i = 0; i < num_of_nodes; i++) {
		printf("%d ", st[i]);
	}
	printf("\n\n");
	return 0;
}


int main(void) {
	Heap st = NULL; // 동적 배열을 통한 스택 구현

	int num_of_nodes = 0;
	/*
	배열 구현에서 cur_size 역할, 즉 스택에 얼마나 많은 원소가 있는지를 나타냄
	또한, 가장 최근에 입력된 원소의 인덱스 값이기도 함.
	*/

	insert(&st, 1, &num_of_nodes);
	insert(&st, 3, &num_of_nodes);
	insert(&st, 4, &num_of_nodes);

	level_order_traversal(st, num_of_nodes); // 4 3 1

	insert(&st, 5, &num_of_nodes);
	level_order_traversal(st, num_of_nodes); // 5 4 1 3

	insert(&st, 2, &num_of_nodes);
	level_order_traversal(st, num_of_nodes); // 5 4 1 3 2

	Delete(&st, &num_of_nodes);
	level_order_traversal(st, num_of_nodes); // 4 3 1 2
	Delete(&st, &num_of_nodes);
	level_order_traversal(st, num_of_nodes); // 3 2 1
	Delete(&st, &num_of_nodes);
	level_order_traversal(st, num_of_nodes); // 2 1
	Delete(&st, &num_of_nodes);
	level_order_traversal(st, num_of_nodes); // 1

	free(st);
}