Lab11 Max Heap 코드

전체 코드

#include <stdio.h>
#include <stdlib.h>
#define INF 1e9 // 1e9 = (1 * 10^9) = 1000000000, 무한대를 나타내는 말

typedef struct HeapStruct {
	int Capacity; // 힙의 최대 수용량
	int Size; // 현재 들어있는 element의 개수
	int* Elements;
}Heap;

Heap* CreateHeap(int heapSize);
void Insert(Heap* heap, int value);
int Find(Heap* heap, int value);
int DeleteMax(Heap* heap);
void PrintHeap(Heap* heap); // level-order로 출력
int IsFull(Heap* heap); // Capacity와 Size 비교

int main(void) {
	char cv;
	Heap* maxHeap;
	int heapSize, key, max_element;

	while (1) {
		scanf("%c", &cv);
		switch (cv) {
		case 'n':
			scanf("%d", &heapSize);
			maxHeap = CreateHeap(heapSize);
			break;
		case 'i':
			scanf("%d", &key);
			Insert(maxHeap, key);
			break;
		case 'd':
			if (maxHeap->Size == 0) { // Heap이 비어있는 상태에서 Deletion을 수행하는 경우 에러메시지 출력
				printf("delete error : heap is empty\n");
				break;
			}
			else {
				max_element = DeleteMax(maxHeap);
				if (max_element != -INF) {
					printf("max element : %d deleted\n", max_element);
				}
			}
			break;
		case 'p':
			PrintHeap(maxHeap);
			break;
		case 'f':
			scanf("%d", &key);
			if (Find(maxHeap, key))
				printf("%d is in the heap\n", key);
			else
				printf("finding error : %d is not in the heap\n", key);
			break;
		case 'q':
			return;
		}
	}

	return 0;
}

Heap* CreateHeap(int heapSize) { // 입력받은 Size를 이용해 힙 생성
	Heap* maxHeap = (Heap*)malloc(sizeof(Heap));

	maxHeap->Capacity = heapSize;
	maxHeap->Size = 0;
	maxHeap->Elements = (int*)malloc(sizeof(int) * (heapSize + 1));

	return maxHeap;
}

void Insert(Heap* heap, int value) {
	if (IsFull(heap)) { // Heap이 꽉 찬 경우 에러메시지 발생
		printf("insert error : heap is full\n");
		return;
	}

	if (Find(heap, value)) { // 이미 존재하는 key를 insert할 시 에러메시지 발생
		printf("insert error : % d is already in the heap\n", value);
		return;
	}

	int i;
	i = ++(heap->Size);

	/* heap->Elements[1 / 2]가 될 경우 무한루프가 발생해서 따로 조건문을 설정했다.
	   heap->Elements[0]에는 아무 값도 없으니까. 
	   또 루트 노드를 삽입할 때는 그냥 바로 삽입해야 하므로 (i != 1) 이라는 조건문도 따로 넣었다. */
	for (i; (i != 1) && heap->Elements[i / 2] < value; i /= 2)
		heap->Elements[i] = heap->Elements[i / 2];
		// 부모 노드와 비교하면서, 부모 노드의 값이 새로운 노드의 값보다 작으면 자리 교체

	heap->Elements[i] = value;
	printf("insert %d\n", value);
}

int Find(Heap* heap, int value) {
	for (int i = 1; i <= heap->Size; i++) {
		if (heap->Elements[i] == value)
			return 1; // value값 찾았으면 1 리턴
	}
	return 0; // 못 찾았으면 0 리턴
}

int DeleteMax(Heap* heap) {
	int parent, child;
	int maxElement, lastElement;

	parent = 1;
	child = 2;

	maxElement = heap->Elements[1]; // return해줄 Max값 저장
	lastElement = heap->Elements[(heap->Size)--]; // 마지막 노드 값 lastElement에 저장하고 사이즈 1 감소(마지막 노드 지워버림)

	heap->Elements[1] = lastElement; // 루트 노드 삭제하고 맨 마지막 노드 값으로 변경

	while (child <= heap->Size) {

		/* 밑의 If문에서 child < heap->Size 조건이 있는 이유는,
		   child < heap->Size 가 아니면 parent 노드의 오른쪽 자식은 없는 것이기 때문이다.
		   예를 들어 heap->Size가 8인데(= 8번째 노드가 마지막인데) 4번째 노드의 오른쪽 자식이 있을 수 있겠는가? */

		if (child < heap->Size && heap->Elements[child] < heap->Elements[child + 1])
			child++; // 왼쪽 자식 노드와 오른쪽 자식 노드 중 더 큰 값을 가지는 자식 노드를 택함

		if (lastElement >= heap->Elements[child])
			break; // 원래 마지막 노드 값(루트 노드 삭제 후 새로 루트 노드가 된 값)이 자식 노드의 값보다 크다면 반복문 탈출

		/* 부모 노드의 값과 자식 노드의 값 교환 */
		heap->Elements[parent] = heap->Elements[child];
		heap->Elements[child] = lastElement;

		parent = child; // level을 1 감소시켜 부모 노드의 값과 자식 노드의 값을 다시 비교하도록 함
		child *= 2;
	}

	return maxElement; // 최댓값이었던 노드 return
}

void PrintHeap(Heap* heap) {
	if (heap->Size == 0) { // Heap이 비어있는 상태에서 Deletion을 수행하는 경우 에러메시지 출력
		printf("print error : heap is empty\n");
		return;
	}

	for (int i = 1; i <= heap->Size; i++)
		printf("%d ", heap->Elements[i]);

	printf("\n");
}

int IsFull(Heap* heap) {
	if (heap->Size == heap->Capacity)
		return 1;
	else
		return 0;
}