9.5 히프 정렬 프로그램

//히프 정렬 프로그램
#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;
}

//위에까진 최대 히프 코드
//우선순위 큐인 히프를 이용한 정렬
void heap_sort(element a[], int n)
{
	int i;
	HeapType* h;

	h = create();
	init(h);
	for (i = 0;i < n;i++) {
		insert_max_heap(h, a[i]);
	}
	for (i = (n - 1);i >= 0;i--) {
		a[i] = delete_max_heap(h);
	}
	free(h);
}

#define SIZE 8

int main(void) {
	element list[SIZE] = { 23,56,11,9,56,99,27,34 };
	heap_sort(list, SIZE);
	for (int i = 0; i < SIZE; i++) {
		printf("%d ", list[i].key);
	}
	printf("\n");
	return 0;
}