Heap Sort

문제

아래의 데이터에 대해 Heap sort algorithm을 이용하여 오름차순으로 정렬하는 프로그램을 구현하시오.

1. Heap sort algorithm을 이용하여 정렬했을 때의 실행 결과(오름차순 정렬)가 출력되도록 구현한다.
2. Max heap 구조를 이용한다

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

//데이터 정의
typedef struct {
	int key;
} element;

//힙 정의
typedef struct {
	element heap[MAX];
	int size;
} Heap;

//힙 생성
Heap* create() {
	return (Heap*)malloc(sizeof(Heap));
}

//초기화
void init(Heap* h)
{
	h->size = 0;
}

//삽입
//현재 요소의 개수가 heap_size인 히프 h에 item을 삽입
void insert(Heap* h, element item)
{
	int i;
	i = ++(h->size);

	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(Heap* h)
{
	int parent, child;
	element item, temp;

	item = h->heap[1];
	temp = h->heap[(h->size)--];
	parent = 1;
	child = 2;

	while (child <= h->size) {
        //현재 노드의 자식 노드 중 더 큰 자식 노드를 찾기
		if ((child < h->size) && h->heap[child].key < h->heap[child + 1].key)
			child++;

		if (temp.key >= h->heap[child].key) 
			break;

        //한 단계 아래로 이동
		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}

//힙 정렬
void heap_sort(element a[], int n)
{
	int i;
	Heap* h;

	h = create();
	init(h);
	//힙에 배열에 있는 데이터 차례대로
	for (i = 0; i < n; i++) {
		insert(h, a[i]);
	}
	//힙에서 하나씩 삭제(최대값이 차례대로 삭제되므로, 삭제되면서 나오는 데이터는 내림차순으로 정렬된다.)
	for (i = (n - 1); i >= 0; i--) {
		a[i] = delete(h);
	}
	free(h);
}

int main(void)
{
	element li[15] = { 2,4,125,105,102,91,88,60,14,31,12,25,82,51,30 };
	printf("정렬할 데이터 : 2 4 125 105 102 91 88 60 14 31 12 25 82 51 30\n");
	
	heap_sort(li, 15);

	printf("\nHeap Sort: ");
	for (int i = 0; i < 15; i++) {
		printf("%d ", li[i].key);
	}
	printf("\n");
}