(자료구조) 대학수업 Max Heap, Level Order Traversal

김규회·2022년 4월 26일
0

과제 #13
단계 1. 파일 (in.txt)로 주어진 정수들을 차례대로 max heap 에 모두 insertion 한 후, 결과로 얻어진 max
heap 을 level order traversal 하여 화면에 출력하라.
단계 2. scanf 로 ‘k’값을 입력 받아, 단계 1 에서 구성된 max heap 에서 k 번 delete 한 뒤, 결과로 얻어진
heap 의 내용을 level order traversal 하여 화면에 출력하라.
<in.txt 형식>
m1 m2 m3 … mn
(여기에서 mi는 임의의 정수)

예제

in.txt
5 3 1 2 4 6
<화면출력>
학부: … 학번:… 이름: …
6 4 5 2 3 1
Scanf_s : 1
5 4 1 2 3

in.txt
1 2 3 4 5 6
<화면출력>
학부: … 학번:… 이름: …
6 4 5 1 3 2
Scanf_s : 2
4 3 2 1

풀이과정

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

#define MAX_ELEMENTS 200
#define HEAP_FULL(n)(n==MAX_ELEMENTS-1)
#define HEAP_EMPTY(n)(!n)
#define MAX_QUEUE_SIZE 100


typedef struct {
	int key;
}element;


element heap[MAX_ELEMENTS];
int n = 0;




void push(element item, int* n);
element pop(int* n);


int main() {
	printf("김규회\n");
	element data[100];
	int cnt= 0;
	
	FILE* fp;
	fopen_s(&fp, "in.txt", "r");
	if (fp == NULL) {
		return 0;
	}
	while (!feof(fp)) {
		fscanf_s(fp, "%d", &data[cnt]);
		//printf("%d ", data[cnt]);
		cnt++;	
	}
	for (int i = 0; i < cnt; i++) {
		push(data[i],&n);
	}
	for (int i = 1; i <=cnt; i++) {
		printf("%d ", heap[i]);
	}
	printf("\n");
	int j = 0;
	int num = 0;
	printf("scanf_s : ");
	scanf_s("%d", &num, sizeof(num));
	
	for (int i = 1; i <=num; i++) {
		pop(&n);
	}
	
	
	for (int i = 1; i <=cnt-num; i++) {
		printf("%d ", heap[i]);
	}

}

void push(element item, int* n) {
	int i;
	if (HEAP_FULL(*n)) {
		fprintf(stderr, "The heap is full.\n");
		exit(EXIT_FAILURE);
	}
	i = ++(*n);
	while ((i != 1) && (item.key > heap[i / 2].key)) {
		heap[i] = heap[i / 2];
		i /= 2;
		
	}
	heap[i] = item;
	
}

element pop(int* n) {
	int parent, child;
	element item, temp;
	if (HEAP_EMPTY(*n)) {
		fprintf(stderr, "The heap is empty\n");
		exit(EXIT_FAILURE);
	}
	item = heap[1];
	temp = heap[(*n)--];
	parent = 1;
	child = 2;
	while (child <= *n) {
		if ((child < *n) && (heap[child].key < heap[child + 1].key)) {
			child++;
		}
		if (temp.key >= heap[child].key) {
			break;
		}
		heap[parent] = heap[child];
		parent = child;
		child *= 2;
	}
	heap[parent] = temp;
	return item;
}

주의해야할 점 Max Heap을 삽입하고 Level Order Traversal 개념을 모른다면 힘들꺼같다. 개념만 이해한다면 풀기 쉬운 문제이다.

풀이 결과

profile
프론트엔드 Developer

0개의 댓글