과제 #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 개념을 모른다면 힘들꺼같다. 개념만 이해한다면 풀기 쉬운 문제이다.
풀이 결과