[정렬 알고리즘] 힙 정렬

힙정렬은 이진 힙 자료구조 기반의 정렬 기술입니다.

이것은 최대값 원소를 찾아 맨 끝에 위치시키는 점에서 선택정렬과 닮았습니다.

 

이진 힙이란? Binary Heap

먼저 완전 이진 트리를 정의해봅시다.

완전 이진 트리는 모든 레벨에서 마지막 리프를 제외하고 꽉차있고 마지막 노드는 왼쪽부터 채워집니다.

 

이진 힙은 아이템이 특정한 순서에 따라 저장되어있는 완전 이진트리입니다. 부모노드는 자식노드 보다 큰 값(작은값)을 갖습니다. 큰값을 갖는 경우 최대 힙이라고 하며, 작은 값을 갖는 경우 최소힙이라고 합니다.

힙은 이진트리나 배열로 구현할 수 있습니다.

 

이진 힙은 완전 이진 트리기 때문에 배열로 표현하더라도 공간이 낭비되지 않습니다. 배열로 쉽게 구현이ㅣ 가능합니다.

부모 노드의 인덱스를 i라 하면 왼쪽 자식 노드는 2*i+1 오른쪽 자식 노드는 2*i +2로 표현할 수 있습니다. (시작 인덱스가 0부터 시작하는 경우)

 

오름차순으로 정렬하기 위한 힙 정렬 알고리즘

1. 주어진 값으로 최대힙을 구성합니다.
2. 가장 큰 원소는 힙의 루트에 저장되어 있습니다. 루트값을 제일 뒤로 보내고 힙 사이즈를 1 줄입니다.
   제일 뒤로 보내 힙에서 제외한다는 의미입니다.
3. 힙의 크기가 1이 될때까지 반복하면 큰 순서대로 뒤에서부터 쌓이게 되어 오름차순으로 정렬됩니다.

힙을 만들 때 노드의 자식은 모두 힙구조여야 하므로 상향식으로 만들어져야 합니다.

 

#include <iostream> 

using namespace std; 

//arr의 인덱스인 i를 루트로 하는 서브 트리를 힙화 합니다.
//n은 힙의 크기입니다.  
void heapify(int arr[], int n, int i) 
{ 
	int largest = i; // 가장 큰 값 인덱스 
	int left = 2*i + 1; // left = 2*i + 1 왼쪽 자식 인덱스 
	int right = 2*i + 2; // right = 2*i + 2 오른쪽 자식 인덱스 

	//만약 왼쪽 자식이 루트보다 크다면 
	if (left < n && arr[left] > arr[largest]) 
		largest = left; 

	//오른쪽 자식이 largest보다 더 큰경우 
	if (right < n && arr[right] > arr[largest]) 
		largest = right; 

	//가장 큰 값이 루트가 아니라면 
	if (largest != i) 
	{ 
		//값을 바꾼다. 
		swap(arr[i], arr[largest]); 

		//그 아래 서브 트리도 똑같이 힙화 한다.
		//하향식 
		heapify(arr, n, largest); 
	} 
} 

void heapSort(int arr[], int n) 
{ 
	//힙 구조 만들기 (배열 재배치) 
	for (int i = n / 2 - 1; i >= 0; i--) 
		heapify(arr, n, i); 

	//힙으로 부터 원소 하나씩 추출 
	for (int i=n-1; i>=0; i--) 
	{ 
		//루트 값을 끝으로 이동 
		swap(arr[0], arr[i]); 

		//최대 힙구조로 설정 
		heapify(arr, i, 0); 
	} 
} 

void printArray(int arr[], int n) 
{ 
	for (int i=0; i<n; ++i) 
		cout << arr[i] << " "; 
	cout << "\n"; 
} 

int main() 
{ 
	int arr[] = {12, 11, 13, 5, 6, 7}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	heapSort(arr, n); 

	cout << "Sorted array is \n"; 
	printArray(arr, n); 
} 

 

힙정렬은 제자리 정렬이다.

힙정렬은 안정정렬이 아니다.

 

힙정렬의 시간 복잡도는 O(n log(n))이다.

 

"힙 구조를 이용해 정렬을 한다. Max heap을 만든 뒤 가장 위의 값을 맨 뒤로 보낸뒤 힙 크기를 1 줄이고, 다시 가장 위의 루트를 힙의 끝으로 보내고 1을 줄이고 반복한다. 힙의 크기가 1이 되면 주어진 배열이 모두 정렬되어 있다."