[알고리즘] C언어- 힙 정렬(heap sort)

 

코드

#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; // 힙 사이즈 0으로 초기화
}

void insert_max_heap(HeapType* h, element item) {
	int i;
	i = ++(h->heap_size); // 힙 사이즈 1증가

	// 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
	while ((i != 1) && (item.key > h->heap[i / 2].key)) { // 1번지가 아니고 새로 삽입하는 key 값이 부모의 key값 보다 크다면
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}

	h->heap[i] = item; // h가 가리키고 있는 힙의 i번지에 새로운 노드를 삽입
}

element delete_max_heap(HeapType* h) {
	int parent, child;
	element item, temp;

	item = h->heap[1]; // 루트 값 보관
	temp = h->heap[(h->heap_size)--]; // 말단 노드 값 보관, 힙 사이즈 1감소
	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 print_heap(HeapType* h) {
	for (int i = 1; i <= h->heap_size; i++)
		printf("%3d", h->heap[i].key);
	printf("\n");

}

// 힙 정렬
void heap_sort(element a[], int n) {
	HeapType* h;
	h = create();
	init(h);
	printf("\n\t--힙트리 생성--\n");
	for (int i = 0; i < n; i++) {
		insert_max_heap(h, a[i]);
		print_heap(h);
	}

	printf("\n\t--힙정렬 수행--\n");
	for (int i = (n - 1); i >= 0; i--) {
		a[i] = delete_max_heap(h);
		print_heap(h);
	}
	free(h); // h 반납 
}
#define SIZE 8
int main(void) {
	element list[SIZE] = { 23,56,11,9,56,99,27,34 }; // 힙은 동일한 값이 들어갈 수 있음

	heap_sort(list, SIZE);

	printf("\n\t--힙정렬 완료(오름차순 정렬)--\n");
	for (int i = 0; i < SIZE; i++) {
		printf("%3d", list[i].key);
	}
	printf("\n");
}

 

 

 

실행 결과