DataStructure,Algorithm] 힙정렬(HeapSort)

입력 받은 배열을 O(n)으로 히프 트리 구조로 생성할 수 있지만, 

여기서는 일단 O(nlogn)으로 진행되는 히프트리 구성을 실시했다.

(이 부분에 대해서는 차후 포스팅할 생각)

최대 히프트리를 구현했고, 최대 히프트리를 바탕으로 오름차순 정렬을 하는 코드다.

내림차순 정렬을 보고 싶다면, list 배열에 넣는 인덱스 순서만 바꿔주면 되고

공부 삼아 최소 히프트리를 구현하는 것도 나쁘지 않을 것이다.

숙련자가 보기에는 이 소스는 잘 짜여진 소스는 아니라는 것을 말해주고 싶다.

처음 자료구조를 배우던 시절 구조에 대해서만 깨우치고 만든 소스라서,

불필요한 메모리 할당도 있고 히프 트리 구성에서 시간 복잡도 손실을 보기는 하지만,

히프트리를 바탕으로 힙정렬(혹은 히프정렬)을 구현하는 것까지는 문제되지 않아 이렇게 포스팅으로 올린다.

#include <stdio.h>
#include <stdlib.h>

#define MAXELEMENT 200

typedef int element;
typedef struct {
	element heap[MAXELEMENT];
	int size;
} HeapType;

void Init(HeapType* h)
{
	h->size = 0;
}
void InsertMaxHeap(HeapType* h, element key)
{
	int i;
	i = ++h->size;

	while (i != 1 && key > h->heap[i / 2])
	{
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = key;
}
element DeleteMaxHeap(HeapType* 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] < h->heap[child + 1])
			child++;
		if (temp >= h->heap[child])
			break;

		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}
void HeapSort(element list[], int n)
{
	int i;
	HeapType h;

	Init(&h);
	for (i = 0; i < n; i++)
		InsertMaxHeap(&h, list[i]);

	for (i = n - 1; i >= 0; i--)
		list[i] = DeleteMaxHeap(&h);
}
void PrintArray(element list[], int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ", list[i]);
	printf("\n");
}
int main(void)
{
	int n;

	printf("요소의 개수: ");
	scanf_s("%d", &n);

	element* arr = (element*)malloc(sizeof(element)*n);
	for (int i = 0; i < n; i++)
		scanf_s("%d", &arr[i]);

	printf("정렬 이전 레코드 상태 : ");
	PrintArray(arr, n);

	HeapSort(arr, n);

	printf("정렬 이후 레코드 상태 : ");
	PrintArray(arr, n);

	free(arr);
}