히프 정렬(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;
}
>>