Complete Binary Tree, Max Heap

Complete Binary Tree

Definition:
A binary tree with n nodes and depth k is complete iff its nodes correspond to the nodes numbered from 1 to n in the full binary tree of depth k.

tree depth가 k인 트리가 k-1까지 full binary tree, k번째 계층은 왼쪽부터 오른쪽으로 node가 있으면 complete binary tree라고 부른다.

과제#15 (만점: 10 점)
단계 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는 임의의 정수)

#include <iostream>
#include <fstream>
#define MAX_ELEMENTS 200
#define HEAP_FULL(n) (n==MAX_ELEMENTS-1)
#define HEAP_EMPTY(n) (!n)

using namespace std;

typedef struct treeNode* treePointer;
typedef struct treeNode {
	int key;
}element;
element heap[MAX_ELEMENTS];
int n = 0;

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)--]; heap[(*n) + 1].key = 0;
	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;
}
int main() {
	int e; int k;
	fstream in("in.txt");

	while(!in.eof()) {
		element temp;
		in >> temp.key;
		push(temp, &n);
	}
	for (int i = 1;heap[i].key; i++) {
		printf("%d ", heap[i].key);
	} //단계 1 끝
	printf("\n");
	scanf_s("%d", &k);
	for (int i = 0; i < k; i++) {
		pop(&n);
	}
	for (int i = 1; heap[i].key; i++) {
		printf("%d ", heap[i].key);
	} //단계 2 끝
}