[알고리즘-기초] 힙(Heap) 정렬

힙 정렬

힙 정렬의 시간복잡도는 으로 빠른 정렬에 속한다.

퀵 정렬은 최악의 경우 의 성능을 내지만, 힙 정렬은 안정적인 성능을 발휘한다. 또한 추가적인 배열을 사용하지 않아 메모리 측면에서도 이점을 보인다.(In Place정렬)

완전 이진트리에서 파생된 heap 특성을 사용하여 정렬하는 알고리즘으로 힙은 부모의 값이 자식의 값보다 항상 크거나 항상 작다라는 조건을 만족하는 완전이진트리 형태의 자료구조이다.

완전이진트리는 자식 노드를 왼쪽부터 채워나가는 형태의 자료구조이다.

힙의 개념

완전이진트리와의 차이점은 큰 값이 상위, 작은 값이 하위에 위치한 트리형 자료구조로써 부모-자식 관계가 일정해야 한다. 작은 값이 부모가 되는 힙 형태를 min-heap(최소 힙), 큰 값이 부모가 되는 트리 구조를 max-heap(최대 힙)이라고 한다.

힙은 다음과 같은 관계를 가지고 있다.

부모 → a[ ( i - 1) / 2]
왼쪽 자식 → a[i * 2 + 1]
오른쪽 자식 → a[ i * 2 + 2]

구현과정

1
2
3
4
5
6

public static void main(String[] args) {
     // Test code
    int[] arr = {5, 3, 2, 7, 1, 4, 6};
    heapSort(arr);
    System.out.println("힙 정렬: " + Arrays.toString(arr));
}
Colored by Color Scripter

cs

1. 배열을 이등분하여 좌측 요소부터 1씩 감소시키면서 heap 형태로 변환한다.

1
2
3

for (int i = arr.length / 2 - 1; i >= 0; i--) {
    heapify(arr, i, arr.length);
}
Colored by Color Scripter

cs

정렬하려는 데이터 {5, 3, 2, 7, 1, 4, 6}을 수행하면 다음과 같은 결과가 나온다.

1
2
3

[5, 3, 6, 7, 1, 4, 2]
[5, 7, 6, 3, 1, 4, 2]
[7, 5, 6, 3, 1, 4, 2]

cs

인덱스 2의 자식 노드 5, 6

인덱스 1의 자식 노드 3, 4

인덱스 0의 자식 노드 1, 2

각각 3개의 데이터 중에 가장 큰 값이 좌측으로 이동한 것을 확인할 수 있다.

2. (1)의 과정을 수행하면, 이등분의 left부분은 heap 상태가 되어지면서 정렬 상태가 되어있을 것이다.

배열의 첫번째 요소(가장 큰 값)와 정렬되지 않은 우측 요소부터 heap 형태로 변환하는 과정을 반복한다.

즉, 위 heapify 에 의해 가장 큰 수가 0 번에 위치하게 되었으므로 오름차순 정렬을 위해 제일 끝 위치랑 swap
그러고 맨 뒤를 제외한 배열을 또 heapify 진행해서 가장 큰 수를 맨 앞으로 보낸 뒤 해당 배열 마지막과 swap

1
2
3
4

for (int i = arr.length - 1; i > 0; i--) {
    swap(arr, 0, i);
    heapify(arr, 0, i);
}
Colored by Color Scripter

cs

 

1
2
3
4
5
6

[6, 5, 4, 3, 1, 2, 7]
[5, 3, 4, 2, 1, 6, 7]
[4, 3, 1, 2, 5, 6, 7]
[3, 2, 1, 4, 5, 6, 7]
[2, 1, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]

cs

 

heap 형태로 변환하는 소스는 다음과 같다. 이진 트리 형태로 배열을 받으면서, root요소를 자식 요소의 값에 따라 계속 바꾸어주는 방식이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// 기존 배열을 heap 자료구조로 바꿔준다.
public static void heapify(int[] arr, int parentIdx, int size) {
    // 자식 노드에 대한 위치
    int leftIdx = parentIdx * 2 + 1; // parentIdx 가 0 까지 들어오므로 + 1
    int rightIdx = parentIdx * 2 + 2;
    int maxIdx = parentIdx;
 
    if (leftIdx < size && arr[maxIdx] < arr[leftIdx]) {
        maxIdx = leftIdx;
    }
 
    if (rightIdx < size && arr[maxIdx] < arr[rightIdx]) {
        maxIdx = rightIdx;
    }
 
    // leftIdx, rightIdx 가 더 커서 교체가 됐을 때
    if (parentIdx != maxIdx) {
        swap(arr, maxIdx, parentIdx);
 
        // swap 된 부분 기준으로 그 밑에 더 자식 노드가 있다면 재귀적으로 진행
        heapify(arr, maxIdx, size); 
    }
}
 
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
Colored by Color Scripter

cs