힙 정렬(Heap Sort)

• 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법.
• 분할정복 알고리즘
• 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성함.
  • 최대힙 : 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙
  • 최소힙 : 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙
• 시간 복잡도가 좋은 편
• 전체 자료를 정렬하는 것보다 배열 중 큰 값을 색출해낼 때 유용
• 힙의 특성을 이용해 우선순위 큐(Priority Queue)나 힙 정렬을 만들 수 있음.

힙(Heap) 이란?

최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete Binary Tree)를 기본으로 한 자료구조.

• 완전이진트리?
• 마지막 레벨을 제외하고 모든 노드가 채워진(자식 노드 2개를 가진) 이진트리.
• 높이가 n인 이진트리의 노드 개수는 2^n-)보다 크거나 같고 (2^n)-1보다 작거나 같다.
• 힙은 두가지 조건을 만족하는 자료구조.
  1. 완전 이진 트리의 형태
  2. 부모의 값은 항상 자식보다 크거나(Max Heap) 작아야(Min Heap) 함
• 힙에서 부모 노드와 자식 노드와의 관계
• 왼쪽 자식의 인덱스 = 부모의 인덱스 x 2
• 오른쪽 자식의 인덱스 = 부모의 인덱스 x 2 + 1
• 부모의 인덱스 = 자신의 인덱스 / 2
• 루트노드에는 항상 데이터들 중 가장 큰 값(혹은 가장 작은 값)이 저장되어 있기 때문에, 최댓값(혹은 최솟값)을 O(1)안에 찾을 수 있다.
• 트리를 배열로 표현 가능

힙 예시

• 배열로 표현

  index(0)	1	2	3	4	5	6	7	8	9
  	100	19	36	17	3	25	1	2	7

  • index는 1부터 시작.

  • 부모의 인덱스가 n이라면 자식은 2n(왼쪽)과 2n+1(오른쪽)이 된다.

    • 부모의 인덱스가 4(value 17)라면, 자식 인덱스는 8(value 2)과 9(value 7)이다.
    • 부모의 인덱스가 1(value 100)라면, 자식 인덱스는 2(value 19)와 3(value 36)이다.
    • 부모의 인덱스가 9(7)라면, 자식인덱스는 18과 19인데 최대 인덱스가 9이므로 자식은 존재하지 않는다.

힙 데이터 삽입(Heap Insert)

1. 가장 끝 자리에 노드 삽입
2. 그 노드와 부모 노드 서로 비교
3. 규칙(최대힙 or 최소힙)에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환
4. 규칙에 맞을 때 까지 3번 과정 반복

힙 데이터 삭제(Heap Delete)

• 최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있는 특징을 가짐.

1. 루트 노드 제거
2. 루트 자리에 가장 마지막 노드 삽입
3. 루트 자리에 올라간 노드와 자식 노드 비교
4. 조건(최대힙 or 최소힙)에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환
   • 최대힙
     1. 부모보다 더 큰 자식이 없으면 교환하지 않고 끝냄
     2. 부모보다 더 큰 자식이 하나만 있으면 그 자식과 교환
     3. 부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환
   • 최소힙
     1. 부모보다 더 작은 자식이 없으면 교환하지 않고 끝냄
     2. 부모보다 더 작은 자식이 하나만 있으면 그 자식하고 교환
     3. 부모보다 더 작은 자식이 둘 있으면 자식들 중 작은 값과 교환
5. 조건을 만족할 때까지 4의 과정 반복

알고리즘

1. 주어진 배열을 최대힙 or 최소힙으로 만든다.
2. 최대 힙의 루트노드(최댓값)와 말단노드(가장 마지막 요소) 교환
3. 새 루트노드에 대해 최대힙 구성
4. 원소의 개수만큼 2~3단계 반복 수행

시간복잡도

힙 정렬의 시간복잡도는 nlogn

• 이진 트리를 최대 힙으로 만들기 위해 최대 힙으로 재구성하는 과정이 트리의 깊이만큼 이루어진다.
• 구성된 힙으로 힙 정렬을 수행하는데 걸리는 전체 시간으 힙 구성시간과 n개의 데이터 삭제 및 재구성 시간 포함.

힙 구현 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

# define MAX_SIZE 25
# define RAND_RANGE 100

////// 전역변수 선언 
clock_t second = 0;
int data[MAX_SIZE] = {};
int sortedOfMergeArray[MAX_SIZE] = {};
int length = sizeof(data)/sizeof(int); // 배열의 크기

////// 함수 선언
void Swap(int *arr, int a, int b);
void seed_init();
void random_number(int *array, int length);
void printArray(int *array);
void selection_sort(int *array, int length);
void bubble_sort(int *array, int length);
void quick_sort(int *array, int start, int end);
void merge_sort(int *data, int start, int end);
void merge(int *data, int start, int mid, int end);
void heap_sort(int *array, int size);
void heap_heapify(int *array, int size, int i);

int main() {
	seed_init();
		
	// 힙 정렬 
	random_number(data, length);
	printf("\n\nHeap Sort\n");
	printf("정렬 전: ");
	printArray(data);
	second = (int)clock();
	heap_sort(data, length);
	printf("\n정렬 후: ");	
	printArray(data);
	printf("\n데이터 %d개의 정렬 수행시간: %0.4f초\n", length, (float)(clock() - second) /CLOCKS_PER_SEC);
	
	return 0;
}

// 스왑 함수 
void Swap(int *arr, int a, int b) {
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

// 난수에 매번 다른 시드를 주기 위한 함수 
void seed_init() {
	srand((unsigned int)time(NULL));
} 

// 난수 발생 함수 
void random_number(int *array, int length) {
	bool overlapCheck = false; // 원소값 중복체크 변수 
	 
	for(int i=0; i<length; i++) {
		while(true) {
			array[i] = (rand()%RAND_RANGE)+1;
			overlapCheck = false;
			
			for(int j=0; j<i; j++) {
				if(array[j] == array[i]) {
					overlapCheck = true;
					break;
				}
			}
			if(!overlapCheck) {
				break;
			}
		}	
	}	
}

// 배열 출력 
void printArray(int *array) {
	for(int i=0; i<length; i++) {
		printf("%d ", array[i]);
	}
	
}

// 힙 정렬 최대 최소힙 만들기 
void heap_heapify(int *array, int size, int i) {
	int left = 2*i+1; 
	int	right = 2*i+2; 
	int	largest = i;
	
	// array[left]>array[largest], array[right]>array[largest] => 최소힙
	//array[left]<array[largest], array[right]<array[largest] => 최대힙 
	
	// 해당 노드가 largest보다 크면 교환 
	if( left<size && array[left] < array[largest] ) {
		largest=left;
	}
	// 해당 노드가 largest보다 크면 교환 
	if( right<size && array[right] < array[largest] ) {
		largest=right;
	}
	if( largest == i ) { 
		return;
	}
	Swap(array, i, largest);
	
	heap_heapify(array, size, largest);
}

// 힙 정렬 
void heap_sort(int *array, int size) {
	for(int i=size/2-1; i>=0; i--) {
		heap_heapify(array, size, i);	
	}
	
	for(int i=size-1; i>=0; i--) {
		Swap(array, 0, i);
		heap_heapify(array, i, 0);
	}
}

결과

---