[Algorithm] 힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

힙 정렬은 시간 복잡도가 O(NlogN)인 정렬으로, 버블 / 선택 / 삽입 정렬에 비해 우수한 성능을 가지고 있다.

 

우선 힙 정렬을 살펴보자.

힙은 자료구조 중 하나로, 이 'Heap' 자료구조의 특성을 활용한 정렬 방법이다.

힙은 완전 이진트리의 일종으로, 여러 값들 중에서 최솟값 혹은 최댓값을 빠르게 찾기 위해 설계된 자료구조이다.

힙은 느슨한 정렬 상태(반 정렬 상태)를 유지하고, 이를 쉽게 풀이하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.

부모 노드의 키 값이 자식 노드의 키 값보다 큰 지, 작은 지에 따라 힙의 종류가 나뉜다.

- 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 큰 힙 → 루트 노드에 가장 큰 원소가 위치하게 된다.

- 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작은 힙 → 루트 노드에 가장 작은 원소가 위치하게 된다.

 

 

힙 정렬의 알고리즘을 단순하게 나타내면 다음과 같다.

1. 정렬하고자 하는 배열을 힙으로 만든다. (이 과정을 heapify라고 한다.)
2. 정렬된 원소들이 저장될 새로운 배열을 생성한다. (이 배열을 정렬 배열이라 부르자.)
3. 힙의 루트노드의 값을 정렬 배열에 append하고, 루트 노드의 값을 삭제한다.
4. 삭제 한 후 나머지 트리에 대해서 다시 힙으로 만든다. (heapify)
5. 힙에 남은 원소가 하나도 없을 때까지 3~4번 과정을 반복한다.
6. 힙에 남은 원소가 없으면, 정렬 배열 속 원소들은 모두 정렬이 되어있다. (Min Heap의 경우 오름차순, Max Heap의 경우 내림차순으로 정렬이 된다.)

 

힙 정렬 파이썬 코드

	"""
	힙 정렬 (Heap sort)
	정렬하고자 하는 배열을 힙 자료구조로 만들고, 이의 특성을 이용한 정렬
	"""
	def heapify(li, idx, n):
	# li : 힙으로 만들고자 하는 배열
	# idx : 선택된 노드
	# n : 힙의 범위
	# 자식의 왼쪽 노드를 의미
	left = idx * 2
	# 자식의 오른쪽 노드를 의미
	right = idx * 2 + 1
	s_idx = idx
	# 선택 노드, 선택 노드의 양 자식 중 가장 작은 값을 찾는 과정
	if left <= n and li[s_idx] > li[left]:
	s_idx = left
	if right <= n and li[s_idx] > li[right]:
	s_idx = right
	# 선택 노드와 자식 노드의 위치가 바뀌어야 한다면
	if s_idx != idx:
	# 부모 자식 위치 변경
	li[idx], li[s_idx] = li[s_idx], li[idx]
	# 부모가 자식으로 내려간 이후에도, 그 자식과 바뀔 여지가 있는지 재귀로 체크
	return heapify(li, s_idx, n)
	def heap_sort(array):
	n = len(array)
	# 루트노드는 index 1부터 시작하므로, 앞에 0 원소를 추가한 채로 시작.
	array = [0] + array
	# 최종 정렬된 원소들이 저장될 배열
	ans = []
	# Min Heap을 만드는 과정
	for i in range(n//2, 0, -1):
	heapify(array, i, n)
	# 루트 노드 원소를 정렬 배열에 저장, heapify 반복
	for i in range(n, 0, -1):
	ans.append(array[1])
	array[i], array[1] = array[1], array[i]
	heapify(array, 1, i-1)
	# array[1:]를 얻으면 오름차순 정렬 배열을 얻을 수 있음
	return ans
	print(heap_sort([3, 4, 5, 2, 1, 6, 7]))

view raw heapsort.py hosted with ❤ by GitHub

 

 

힙 정렬 자바 코드

	/*
	* 힙 정렬 (Heap sort)
	* 정렬하고자 하는 배열을 힙 자료구조로 만들고, 이의 특성을 이용한 정렬
	*/
	private void solve() {
	int[] array = { 7, 3, 4, 2, 1, 5, 6 };
	heapSort(array);
	for (int v : array) {
	System.out.println(v);
	}
	}
	public static void heapify(int array[], int n, int i) {
	int p = i;
	// 자식 왼쪽 노드
	int l = i * 2 + 1;
	// 자식 오른쪽 노드
	int r = i * 2 + 2;
	// 부모, 자식 중 가장 작은 값 탐색
	if (l < n && array[p] > array[l]) {
	p = l;
	}
	if (r < n && array[p] > array[r]) {
	p = r;
	}
	// 부모 자식 관계 바뀌어야 한다면
	if (i != p) {
	// 부모 자식 위치 변경
	swap(array, p, i);
	// 위치 변경 이후에도 그 자식과 변경될 여지 있는지 재귀로 확인
	heapify(array, n, p);
	}
	}
	public static void heapSort(int[] array) {
	int n = array.length;
	// 최소 힙 생성
	for (int i = n / 2 - 1; i >= 0; i--) {
	heapify(array, n, i);
	}
	// 최소 힙에서 추출, 나머지 배열 다시 힙으로 재구성
	for (int i = n - 1; i > 0; i--) {
	swap(array, 0, i);
	heapify(array, i, 0);
	}
	}
	public static void swap(int[] array, int a, int b) {
	int temp = array[a];
	array[a] = array[b];
	array[b] = temp;
	}

view raw heapsort.java hosted with ❤ by GitHub

 

 

힙 정렬 장단점

장점

• 항상 O(NlogN)을 보장
• max 또는 min 값을 구할 때 시간 복잡도는 O(1)이다.

단점

• 일반적으로 속도만 비교하자면 퀵이 평균적으로 더 빠르다. 그래서 잘 사용하지 않음.