힙 정렬(Heap Sort)

힙 정렬(Heap Sort)

힙(heap)을 이용하는 정렬 알고리즘

 

힙(heap) : 부모 노드의 값이 자식 노드의 값보다 큰 완전이진트리

부모 노드의 값이 자식 노드의 값보다 항상 크기 때문에 힙의 루트에는 제일 큰 수가 들어가게 된다.

이를 이용하여 힙의 루트 값을 꺼내어 배열의 오른쪽부터 채워넣으면서(오름차순 기준) 배열을 정렬할 수 있다.

 

힙으로 만들기 -> 배열의 맨 오른쪽부터 루트값 채워넣기 -> 다시 힙으로 만들기 -> 루트값 채워넣기  ...

이렇게 배열의 정렬이 완료될 때까지 힙 만들기와 루트값 넣기를 반복하여 정렬을 한다.

 

 

시간 복잡도 : O(NlogN)

힙으로 만들 때 걸리는 시간 복잡도는 O(NlogN), 힙에서 루트값을 꺼내는데 걸리는 시간 복잡도는 O(1) 이므로

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

 

 

 

[예제]

배열 arr의 요소가 5 9 3 1 8 6 4 7 2 일 때, 이 배열을 오름차순으로 정렬하기

 

배열 arr을 트리 형태로 나타내면 다음과 같다.

 

오른쪽 트리는 아직 힙 상태가 아니다. 부모 노드의 값이 자식 노드의 값보다 작은 경우가 존재하기 때문이다.

따라서 우선 오른쪽의 트리를 힙 상태로 바꿔줘야 한다.

 

힙이 아닌 트리를 힙 상태로 바꾸기

힙이 아닌 것을 힙으로 만들기 위해서 아래(Bottom)에서부터 위(Up)로 올라가며 힙 상태인지 아닌지 체크한다.

만약에 힙 상태가 아니라면 왼쪽 자식 노드 값과 오른쪽 자식 노드 값을 비교하여 더 큰 값과 부모 노드 값을 교환한다.

 

트리의 아래부터 위로 올라가면서 힙 상태가 아닌 것을 찾아보자.

아래 그림에서 빨간색 박스 안의 트리는 힙 상태가 아니다. 부모 노드의 값이 1로, 자식 노드 값인 2와 7보다 작기 때문이다.

 

그러면 자식 노드끼리 비교해보자.

왼쪽 노드의 값은 7, 오른쪽 노드의 값은 2 이므로 왼쪽 노드의 값이 더 크다.

그러므로 왼쪽 노드와 부모 노드를 서로 교환해준다.

1과 7을 교환함으로써 힙 상태가 되었다.

다음으로 아래의 빨간 박스 안의 트리를 보자. 

역시 마찬가지로 부모 노드의 값이 3으로, 자식 노드값인 6과 4보다 작으므로 힙 상태가 아니다.

방금전과 마찬가지로 자식노드끼리 비교해서 더 큰 값과 부모노드를 교환하면 힙 상태로 바뀐다.

이제 올라가서 위쪽을 보면 빨간 박스 안의 부분트리가 힙 상태가 아니다.

자식 노드 값인 9와 6을 비교하면 9가 더 크므로 왼쪽 자식 노드와 부모 노드를 교환한다.

위의 9와 5가 교환됨에 따라 아래의 빨간 박스 부분이 힙 상태가 아니게 된다.

동일한 방법으로 힙으로 만들어 주면 다음과 같다.

 

 

힙(heap) -> 정렬하기

이제 배열 전체를 힙 상태로 만들었다.

아래의 힙에서 루트에 있는 값인 9가 전체 중에서 가장 큰 값이 된다. 배열의 첫번째 요소에 가장 큰 값이 위치한다.

오름차순으로 정렬해야 하므로 루트에 있는 가장 큰 값이 배열의 맨 오른쪽에 있어야 한다.

그러므로 arr[0] = 9를 arr[8] = 2와 서로 교환한다.

배열의 맨 오른쪽 9는 정렬이 완료되었다.(회색칸은 정렬이 완료되었음을 의미)

이제 9를 제외한 arr[0] ~ arr[7] 까지를 다시 힙 상태로 만들면 9 다음으로 큰 값인 8이 루트 노드에 위치하게 된다.

루트 노드에 있는 8을 arr[7] 로 옮기기 위해서 arr[0]과 arr[7]을 교환한다.

다시 힙으로 만들면 루트 노드에 7이 들어간다.

arr[0]을 arr[6]의 값과 교환한다.

 

 

다시 힙으로 만들면 루트 노드에 6이 들어간다.

arr[0]을 arr[5]의 값과 교환한다.

 

 

다시 힙으로 만들면 루트 노드에 5가 들어간다.

arr[0]을 arr[4]의 값과 교환한다.

 

 

다시 힙으로 만들면 루트 노드에 4가 들어간다.

arr[0]을 arr[3]의 값과 교환한다.

 

 

다시 힙으로 만들면 루트 노드에 3이 들어간다.

arr[0]을 arr[2]의 값과 교환한다.

 

 

다시 힙으로 만들면 루트 노드에 2가 들어간다.

arr[0]을 arr[1]의 값과 교환한다.

 

 

arr[1] 까지 정렬을 완료하고 나면 위 과정을 종료한다.

이런식으로 반복적으로 힙을 만들어서 배열을 오름차순으로 정렬할 수 있다.

 

 

 

소스코드 : 

	public static void heapSort(int[] arr, int n) {

		for (int i = (n - 1) / 2; i >= 0; i--)
			makeHeap(arr, i, n - 1);

		for (int i = n - 1; i > 0; i--) {
			swap(arr, 0, i);
			makeHeap(arr, 0, i - 1);
		}
	}

	public static void makeHeap(int[] arr, int left, int right) {

		int root = arr[left]; // 루트 노드
		int parent; // 부모 노드 인덱스
		int child; // 자식 노드 인덱스

		for (parent = left; parent < (right + 1) / 2; parent = child) {

			int cl = parent * 2 + 1; // 왼쪽 자식 노드 인덱스
			int cr = cl + 1; // 오른쪽 자식 노드 인덱스

			child = (cr <= right && arr[cl] < arr[cr]) ? cr : cl;

			if (root > arr[child])
				break;

			arr[parent] = arr[child];
		}
		arr[parent] = root;

	}