#include <stdio.h>
#define MAX_ELEMENT 8

typedef struct {
	int key;
}element;

typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size; // 힙 사이즈가 n이면 heap배열의 원소들이 (idx 1 ~ idx n) 까지 존재 
}HeapType;
typedef HeapType* HeapType_ptr;

// 생성 함수
HeapType_ptr create() {
	return (HeapType*)malloc(sizeof(HeapType));
}

// 초기화 함수
void init(HeapType_ptr h) {
	h->heap_size = 0;
}

// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다.
// 삽입 함수
void insert_max_heap(HeapType_ptr h, int receive) {
	element item;
	item.key = receive;

	int i;
	i = ++(h->heap_size);

	// 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
	// 배열로 트리를 구현하니까 부모 노드의 idx는 1 
	while ((i != 1) && (item.key > h->heap[i / 2].key)) {
		h->heap[i] = h->heap[i / 2]; // 부모를 한 칸 내림 
		i /= 2;
	}
	h->heap[i] = item; // 삽입될 위치가 확실해진 다음에 새로운 노드를 삽입 
}

// 삭제 함수 
element delete_max_heap(HeapType_ptr h) {
	int parent, child;
	element item, temp;

	item = h->heap[1]; // 루트 노드 값을 반환하기 위해 item변수로 옮긴다.
	temp = h->heap[(h->heap_size)--]; // 말단 노드 값을 temp변수로 옮기고 힙 사이즈를 1 줄인다. (처음에는 루트에 위치해있다고 생각) 
	parent = 1;
	child = 2; // 루트의 왼쪽 자식부터 비교한다. 

	// 자식이 힙을 벗어나지 않았으면 반복문 진행 
	while (child <= h->heap_size) {
		// 두 자식노드가 있으면 더 큰 자식노드를 찾는다.
		if ((h->heap[parent * 2].key >= 0) && (h->heap[(parent * 2) + 1].key >= 0)) {
			if ((h->heap[parent * 2].key) > (h->heap[(parent * 2) + 1].key))
				child = parent * 2;
			else
				child = (parent * 2) + 1;
		}
		// 말단 노드를 현재 자식의 부모 노드의 위치에 있다고 생각했을 때, 값이 크거나 같으면 힙 조정할 필요가 X
		if (temp.key >= h->heap[child].key)
			break;
		// 부모 노드 자리에 자식 노드의 키 값을 저장 
		h->heap[parent] = h->heap[child];
		// 한 단계 아래로 이동
		parent = child;
		child *= 2;
	}
	// 루트에 말단 노드를 실제로 저장 (Or) child>h->heap_size로, 위치해야 될 노드에 실제 저장 
	h->heap[parent] = temp;
	return item;
}



int main(void) {
	HeapType_ptr heap = create(); // 최대 힙 생성
	init(heap); // 초기화 
	int n = 7; // 정렬할 숫자의 개수

	// 힙 배열만을 이용해서 정렬하기 (공간복잡도를 최소화한 방법) 
	insert_max_heap(heap,10);
	insert_max_heap(heap, 5);
	insert_max_heap(heap, 4);
	insert_max_heap(heap, 1);
	insert_max_heap(heap, 2);
	insert_max_heap(heap, 3);
	insert_max_heap(heap, 6);


	// n개의 데이터를 가진 최대 힙을 최소 힙으로 만듦 
	for (int i = n; i >= 1; i--) {
		heap->heap[i] = delete_max_heap(heap);
	}
	heap->heap_size = n;

	// 출력
	for (int i = 1; i <= heap->heap_size; i++)
		printf("[%d] ", heap->heap[i]);

	return 0;
}