[Algorithm] 정렬 - 힙 정렬 (Heap Sort)

힙 정렬(Heap Sort)이란?

- 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다.

 

 

작동 방식

[초기 배열]

1) 배열 값 순서대로 부모노드 - 왼쪽 자식 - 오른쪽 자식 순서대로 완전 이진트리를 구성한다.

 

2) 최대 힙이 되도록 힙을 구성한다.

- 자식 노드를 비교하여 더 큰 값을 찾는다.

 

- 부모노드보다 큰 지 비교한 후, 부모노드보다 크면 값을 교환한다.

 

- 루트까지 반복한다.

 

3) 루트와 마지막 단말 노드(자식이 없는 노드) 값을 교체한 후 노드를 제거한다.

4) 변경된 트리를 다시 최대 힙이 되도록 재구성한다. (2~3 반복)

 

2~3번 작업을 반복하게 되면, 최대 힙이 되도록 재구성할 때마다 루트에 최댓값이 오게 된다.

4번 작업을 통해 가장 큰 값이 배열의 가장 오른쪽 끝 인덱스부터 차례대로 위치하게 된다.

 

 

소스코드

#include <iostream>

using namespace std;

void heapSort(int* arr, int len);
void heapify(int* arr, int len, int parent);
void swap(int& a, int& b);

int main() {
	int N;
	cin >> N;

	int* arr = new int[N + 1];
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

	heapSort(arr, N);

	for (int i = 1; i <= N; i++) {
		printf("%d\n", arr[i]);
	}

	delete[] arr;

	return 0;
}

void heapSort(int* arr, int len) {
	// 최대 힙 구성
	for (int i = len / 2; i > 0; i--) {
		heapify(arr, len, i);
	}

	for (int i = len; i > 1; i--) {
		// 마지막 노드 교체
		swap(arr[1], arr[i]);

		// 최대 힙 구성
		heapify(arr, i - 1, 1);
	}
}

void heapify(int* arr, int size, int parent) {
	int left = parent * 2;
	int right = parent * 2 + 1;
	
    // 범위를 벗어난 경우
	if (right > size && left > size) return;

	int max = left;

	// 오른쪽 자식도 있는 경우
	if (left < size) {
		max = arr[left] < arr[right] ? right : left;
	}

	if (arr[parent] < arr[max]) {
		swap(arr[parent], arr[max]);
		heapify(arr, size, max);
	}
}

void swap(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}

 

정렬 방식에 대해 이해하고 나서 처음 코드를 짰을 때에는, 시간초과가 걸렸다. (백준 2751번 문제로 체크)

맨 처음 전체적으로 최대 힙으로 구성한 후, 루트와 마지막 노드를 교환했다.

그 다음 다시 최대 힙으로 구성을 하는데 이 과정에서 bottom-up 방식으로 마지막 노드부터 루트 노드까지 전체적으로 비교를 했던 것이다.

하지만 루트와 마지막 노드만 교환한 것이므로 루트노드 ~ 교환된 쪽 방향의 노드들만 비교하면 된다.

 

 

 

시간복잡도

평균의 경우 : O(nlogn)

최선의 경우 : O(nlogn)

최악의 경우 : O(nlogn)

 

최대 힙으로 구성하는 과정이 트리의 깊이만큼 이루어지므로 O(logn)의 시간이 걸린다.

전체 n개의 데이터에 대해 힙을 재구성하므로 시간복잡도는 O(nlogn)이 된다.

 

 

비교

합병 정렬과 힙 정렬은 시간복잡도가 동일하다.

하지만 합병 정렬은 정렬된 데이터를 저장하기 위한 별도의 공간이 필요하다.

 

빠른 정렬의 최악의 경우 시간복잡도는 O(n²)이지만, 평균적으로 보면 빠른 정렬이 속도가 더 빠르다.

따라서 빠른 정렬 방식이 더 많이 쓰인다.

 

 

참고

https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC