히프 정렬

히프 정렬(heap sort): 히프를 사용하는 정렬 알고리즘

- 최대 히프를 이용하여 n개의 요소를 O(nlog₂n)의 시간 복잡도로 정렬

- 정렬되지 않은 1차원 배열이 존재할 때, 배열의 데이터들을 차례대로 최대 히프에 추가

- 한 번에 하나의 요소를 히프에서 꺼내 배열의 뒤쪽부터 저장

- 배열은 오름차순으로 정렬됨

 

히프 정렬 복잡도

- 히프 트리의 전체 높이는 log₂n이므로 하나의 요소를 히프에 삽입하거나 삭제할 때 히프 재정비에 log₂n만큼의 시간 소요

- 요소의 개수가 n개일 때 전체적으로 O(nlog₂n)의 시간 소요

- 삽입 정렬 알고리즘 시간 복잡도가 O(n²)인 것에 비해 효율적

- 히프 정렬은 전체 자료 정렬 보다는 가장 큰 값 몇 개만이 필요할 때 가장 유용

---

히프 정렬 구현

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

//생성
HeapType* create() {
	return (HeapType*)malloc(sizeof(HeapType));
}
//초기화
void init(HeapType* h) {
	h->heap_size = 0;
}
//삽입
void insert_max_heap(HeapType* h, element item) {
	int i;
	i = ++(h->heap_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_max_heap(HeapType* h) {
	int parent, child;
	element item, temp;

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

	while (child <= h->heap_size) {
		if ((child < h->heap_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;
	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;
}

>>