#include <stdio.h>
#include <time.h>
#define MAX_ELEMENT 100
#define size 99

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;
}

// 리스트로 힙 만들기 
void heapify(HeapType_ptr h, element* a) {
	// 리스트 a를 '완전 이진 트리 배열'로 생각한 뒤 h에 일단 저장 
	h->heap_size = size;
	for (int i = 1; i <= h->heap_size; i++)
		h->heap[i] = a[i];
	// -> 힙 성질을 만족하지 않는 h가 생성됨 

	// 힙 성질을 만족하게 할 첫 번째 서브트리 지정 
	int parent, child, parent_save, child_save;
	child = child_save = h->heap_size; // 말단 노드부터 비교 시작 
	parent = parent_save = h->heap_size / 2;

	// 모든 서브트리에 대해 힙 성질 만족 시키기 
	element temp;
	while (parent > 0) {
		// 현재 부모 노드의 값을 temp로 지정 
		temp = h->heap[parent];
		// 자식이 힙을 벗어나지 않았으면 반복문 진행 
		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;
			}
			// temp 노드를 현재 자식의 부모 노드의 위치에 있다고 생각했을 때,  값이 작거나 같으면 힙 조정할 필요가 X
			if (temp.key <= h->heap[child].key)
				break;
			// 부모 노드 자리에 자식 노드의 키 값을 저장 
			h->heap[parent] = h->heap[child];
			// 한 단계 아래로 이동
			parent = child;
			child *= 2;
		}
		// child>h->heap_size로, 위치해야 될 노드에 저장 
		h->heap[parent] = temp;
		// 서브트리 재지정 
		parent = parent_save = parent_save - 1;
		child = child_save = parent * 2; // p가 1이고 c가2면 전체 노드를 다 보게 됨 
	}
}

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

	item = h->heap[1]; // 루트 노드 값을 반환하기 위해 item변수로 옮긴다.
	temp = h->heap[(h->heap_size)--]; // 말단 노드 값을 temp변수로 옮기고 힙 사이즈를 1 줄인다. (temp값이 처음에는 루트에 위치해있다고 생각) 
	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) {
	// 랜덤값 size개 이용해서 리스트 생성 <인덱스 1부터 size까지 저장> 
	element* list = (element*)malloc(sizeof(element) * (size + 1));
	for (int i = 1; i <= size; i++)
		list[i].key = rand() % 100;

	HeapType_ptr heap = create(); // 힙 생성
	init(heap); // 초기화 

	// 힙 제작 [시간복잡도: O(n)]
	heapify(heap, list);

	// 삭제
	printf("힙 삭제: [ Original Size:%d ]", heap->heap_size);
	for (int i = 1; i <= size; i++)
		printf("\n%d) %d, size:%d", i, (delete_min_heap(heap)).key, heap->heap_size);
	printf("\n");

	free(heap);
}