[Data Structure] 히프 정렬

히프 정렬 (최대 히프)

- n개의 요소를 O(nlog₂n)시간 안에 정렬

 

- 정렬되지 않은 배열 element a[]에 대하여

1. 배열 a의 data들을 최대 히프에 차례대로 추가
2. 최대 히프에서 data들을 하나씩 꺼내서 배열 a의 맨 뒤쪽부터 저장
3. 배열 a에 대한 히프 정렬 완료

void heap_sort(element arr[], int len) {
	heapnode* h;
	h = create();
	init_heap(h);

	for (int i = 0; i < len; i++) {
		insert_node(h, arr[i]);
	}

	for (int i = (len - 1); i >= 0; i--) {
		arr[i] = delete_node(h);
	}
	free(h); // 히프 동적 할당 해제
}

 

 

Full Code

#include <stdio.h>
#include <stdlib.h>
// 히프 정렬
#define MAX_HEAP_SIZE 100

typedef int element; // 히프에 저장된 각 요소들

typedef struct heepnode {
	element heap[MAX_HEAP_SIZE];
	int heap_size;
}heapnode;

heapnode* create() {
	return (heapnode*)malloc(sizeof(heapnode));
}

void init_heap(heapnode* h) {
	h->heap_size = 0;
}

int is_empty(heapnode* h) {
	return h->heap_size == 0;
}

int is_full(heapnode* h) {
	return h->heap_size == MAX_HEAP_SIZE - 1;
}

void insert_node(heapnode* h, element item) {
	if (is_full(h)) {
		fprintf(stderr, "Error : Heap is full\n\n");
		return;
	}
	else {
		int i; // item의 인덱스
		i = ++h->heap_size;
		// item인덱스 = 현재 히프트리에 있는 최종 item 인덱스의 다음 인덱스
		while (i != 1 && (item > h->heap[i / 2])) {
			h->heap[i] = h->heap[i / 2];
			i /= 2;
		}
		h->heap[i] = item;
	}
}

element delete_node(heapnode* h) {
	if (is_empty(h)) {
		fprintf(stderr, "Error : Heap is empty\n\n");
		return;
	}
	else {
		element root = h->heap[1]; // 루트 노드 item
		element last = h->heap[h->heap_size--]; // 말단 노드 item
		// 루트 노드를 삭제시키고 말단을 루트로 올릴거기 때문에 heap_size는 1 감소
		int index = 1; // 말단 노드가 들어가는 index -> 자리 찾을 때 까지 계속 변함
		int child = 2;
		while (child <= h->heap_size) {
			if ((child < h->heap_size) && (h->heap[child] < h->heap[child + 1]))
				child++; // 자식 노드 중 더 큰 값의 인덱스 찾기
			if (last >= h->heap[child]) break;
			// 최종 insert 노드의 값이 해당 인덱스의 자식 값보다 크면 더 이상 옮기기 X
			h->heap[index] = h->heap[child];
			index = child;
			child *= 2;
		}
		h->heap[index] = last;
		return root;
	}
}

void heap_sort(element arr[], int len) {
	heapnode* h;
	h = create();
	init_heap(h);

	for (int i = 0; i < len; i++) {
		insert_node(h, arr[i]);
	}

	for (int i = (len - 1); i >= 0; i--) {
		arr[i] = delete_node(h);
	}
	free(h); // 히프 동적 할당 해제
}

int main(void) {
	element arr[] = { 289, 30, 1, 2, 6, 79, 59, 17,  20, 100};
	int len = sizeof(arr) / sizeof(int);

	printf("배열 요소 개수 : %d\n", len);
	printf("정렬 전 배열 arr 요소 : ");
	for (int i = 0; i < len; i++) {
		printf("[%d] ", arr[i]);
	}
	printf("\n");
	heap_sort(arr, len);
	printf("정렬 후 배열 arr 요소 : ");
	for (int i = 0; i < len; i++) {
		printf("[%d] ", arr[i]);
	}
}