9.4 히프의 구현(히프트리 전체 함수)

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200

typedef struct {
	int key;
}element;
typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size;
}HeapType;

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

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

//heap의 삽입함수
void insert_max_heap(HeapType* h, element item)
{
	int i; //i는 인덱스 번호
	i = ++(h->heap_size);

	//트리를 거슬러 올라가면서 부모노드와 비교하는 단계
	while ((i != 1) && (item.key > h->heap[i / 2].key)) { //i가 루트노드가 아니고+새 노드가 부모노드보다 크면
		h->heap[i] = h->heap[i / 2];//부모노드는 밑으로 끌어내리고
		i /= 2;//i는 부모노드의 위치에 오른다
	}
	h->heap[i] = item; //새로운 노드를 삽입
}

//heap의 삭제함수
element delete_max_heap(HeapType* h)
{
	int parent, child;
	element item = h->heap[1]; //루트노드의 값=item
	element temp = h->heap[(h->heap_size)--]; //루트노드 삭제하고 그 자리에 들어갈 값=temp
	parent = 1;
	child = 2;
	while (child <= h->heap_size) {
		//현재 노드의 자식노드중 더 큰 자식노드를 찾는다
		if((child < h->heap_size) && //형제 노드가 존재하고
			(h->heap[child].key)<h->heap[child+1].key) //형제노드가 더 크다면
			child++; //child=더 큰 형제노드
		if (temp.key >= h->heap[child].key)break; //부모노드>자식노드이면 종료한다

		//한 단계 아래로 이동(부모와 자식을 교환)
		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp; //더이상 올릴 값이 없으면 temp를 저장한다
	return item;
}

int main(void) {
	element e1 = { 10 }, e2 = { 5 }, e3 = { 30 };
	element e4, e5, e6;
	HeapType* heap;

	heap = create(); //히프 생성
	init(heap); //초기화

	//삽입
	insert_max_heap(heap, e1);
	insert_max_heap(heap, e2);
	insert_max_heap(heap, e3);

	//삭제
	e4 = delete_max_heap(heap);
	printf("< %d > ", e4.key);
	e5 = delete_max_heap(heap);
	printf("< %d > ", e5.key);
	e6 = delete_max_heap(heap);
	printf("< %d > \n", e6.key);

	free(heap);
	return 0;

}