C++ / 힙 정렬(Heap Sort)

힙 정렬의 시간 복잡도는 nlog n이다.

 

힙을 생성하는 알고리즘의 시간 복잡도는 log n이다. 그 이유는 완전 이진트리 구조를 사용하기 때문이다.

 

 

상향식 구현방법

#include <iostream>

using namespace std;

int number = 9;
int heap[9] = {7, 6, 5, 8, 3, 5, 9, 1, 6};

int main()
{
	// 힙을 구성
	for(int i = 1; i < number; i++) {
		int c = i;
		do {
			int root = (c - 1) / 2;
			if(heap[root] < heap[c]) {
				int temp = heap[root];
				heap[root] = heap[c];
				heap[c] = temp;
			}
			c = root;
		}while (c != 0);
	}
	
	// 크기를 줄여가며 반복적으로 힙을 구성
	for(int i = number - 1; i >= 0; i--) {
		int temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		int root = 0;
		int c = 1;
		
		do {
			c = 2 * root + 1;
			// 자식 중에 더 큰 값을 찾기
			if(c < i - 1 && heap[c] < heap[c + 1]) {
				c++;
			}
			
			// 루트보다 자식이 크다면 교환
			if(c < i && heap[root] < heap[c]) {
				temp = heap[root];
				heap[root] = heap[c];
				heap[c] =temp;
			}
			root = c;
		} while (c < i);
	}
	
	// 결과 출력
	for(int i = 0; i < number; i++) {
		printf("%d ", heap[i]);
	}
	
	return 0;
}

 

#include <iostream>

using namespace std;

int number = 9;
int heap[9] = {7, 6, 5, 8, 3, 5, 9, 1, 6};

void Up_heapify(int i) {
	int c = i;
	int root = (c - 1) / 2;
	
	if(heap[root] < heap[c]) {
		int temp = heap[root];
		heap[root] = heap[c];
		heap[c] = temp;
	}
	c = root;
	
	if(c != 0) Up_heapify(c);
}

void Down_heapify(int i) {
	// 왼쪽 자식 노드를 가리킵니다.
	int c = 2 * i + 1;
	// 오른쪽 자식 노드가 있고, 왼쪽 자식노드보다 크다면,
	if(c < number && heap[c] < heap[c + 1]) {
		c++;
	}
	// 부모보다 자식이 더 크다면 위치를 교환합니다.
	if(heap[i] < heap[c]) {
		int temp = heap[i];
		heap[i] = heap[c];
		heap[c] = temp;
	}
	
	// number / 2까지만 수행하면 됩니다.
	if(c <= number / 2) Down_heapify(c);
}

int main()
{	
	for(int i = 1; i < number; i++)
		Up_heapify(i);
	
	// for(int i = number / 2; i >= 0; i--)
	// 	Down_heapify(i);

	// 크기를 줄여가며 반복적으로 힙을 구성
	for(int i = number - 1; i >= 0; i--) {
		int temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		int root = 0;
		int c = 1;
		
		do {
			c = 2 * root + 1;
			// 자식 중에 더 큰 값을 찾기
			if(c < i - 1 && heap[c] < heap[c + 1]) {
				c++;
			}
			
			// 루트보다 자식이 크다면 교환
			if(c < i && heap[root] < heap[c]) {
				temp = heap[root];
				heap[root] = heap[c];
				heap[c] =temp;
			}
			root = c;
		} while (c < i);
	}
	
	// 결과 출력
	for(int i = 0; i < number; i++) {
		printf("%d ", heap[i]);
	}
	
	return 0;
}

 

이 알고리즘의 코드는 동빈나 알고리즘의 강의를 듣고 코딩한 것이다.

 

원래 내가 생각하는 힙 정렬 알고리즘이란 막 어지럽혀져있는 배열을 힙이란 곳에 우선순위대로 저장하는 느낌을 생각하였다.

 

하지만 동빈나 알고리즘의 코드는 보통 c 자료구조 서적과는 다르게 일단, heapify를 사용한다.

 

그렇게 함으로써, 힙을 구성한다음 제대로된 정렬?을 거치는 구조이다.

 

 

#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;
}
 
// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다.
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;
}
 
element select_del_heap(HeapType * h, int k) {
	int parent, child;
	int i;
	element temp, item;
 
	for(i = 0; i < h->heap_size; i++)
		if(h->heap[i].key == k)
			break;
 
	item = h->heap[i];
	temp = h->heap[(h->heap_size)--];
	parent = i;
	child = i*2;
 
	while(i <= h->heap_size) {
		if((child != i) && (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;
}
 
int main(void)
{
	element e1 = { 12 }, e2 = { 10 }, e3 = { 8 }, e4 = {4}, e5 = {6}, e6 = {2}, e7 = {5}, e8= {3};
	element tmp = {11};
	HeapType * heap;
 
	heap = create();
	init(heap);
 
	insert_max_heap(heap, e1);
	insert_max_heap(heap, e2);
	insert_max_heap(heap, e3);
	insert_max_heap(heap, e4);
	insert_max_heap(heap, e5);
	insert_max_heap(heap, e6);
	insert_max_heap(heap, e7);
	insert_max_heap(heap, e8);
	insert_max_heap(heap, tmp);
 
	select_del_heap(heap, 8);
 
	printf("%d \n", delete_max_heap(heap).key);
	printf("%d \n", delete_max_heap(heap).key);
	printf("%d \n", delete_max_heap(heap).key);
	printf("%d \n", delete_max_heap(heap).key);
	printf("%d \n", delete_max_heap(heap).key);
	printf("%d \n", delete_max_heap(heap).key);
	printf("%d \n", delete_max_heap(heap).key);
	printf("%d \n", delete_max_heap(heap).key);;
 
	free(heap);
	return 0;
}