힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

힙 정렬은 비교 기반 정렬 알고리즘으로, 이진 힙 자료구조를 활용하여 효율적인 정렬을 수행한다.
시간 복잡도가 안정적이고 추가 메모리를 거의 사용하지 않는 특징을 가지고 있어 많은 시스템에서 널리 사용된다.

힙 정렬은 비교 기반 정렬 알고리즘 중에서 시간 복잡도가 보장되고 추가 메모리를 거의 사용하지 않는 효율적인 알고리즘이다.
최선, 평균, 최악의 경우 모두 O(n log n)의 시간 복잡도를 가지며, 특히 메모리 제약이 있는 환경에서 유용하다.

불안정 정렬이라는 단점이 있지만, 안정성이 중요하지 않은 많은 응용 분야에서 여전히 강력한 선택지이다. 힙 자료구조의 이해는 우선순위 큐, 그래프 알고리즘 등 컴퓨터 과학의 다른 영역에도 도움이 된다.

힙(Heap) 자료구조의 이해

힙 정렬을 이해하기 위해서는 먼저 힙 자료구조에 대한 이해가 필요하다.

힙의 정의

힙은 다음 두 가지 특성을 만족하는 완전 이진 트리이다:

1. 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드들은 왼쪽부터 채워져 있다.
2. 힙 속성(Heap Property):
   • 최대 힙(Max Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같음
   • 최소 힙(Min Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같음

힙의 표현

힙은 일반적으로 배열을 사용하여 표현한다.
이진 트리의 레벨 순서 탐색(level-order traversal)과 같은 방식으로 배열에 저장된다.

배열에서 인덱스 i의 노드에 대해:

• 부모 노드 인덱스: (i-1) // 2 (파이썬 기준)
• 왼쪽 자식 노드 인덱스: 2*i + 1
• 오른쪽 자식 노드 인덱스: 2*i + 2

이러한 규칙을 통해 포인터 없이도 트리 구조를 효율적으로 표현할 수 있다.

힙 정렬 알고리즘의 원리

힙 정렬은 힙의 특성을 활용하여 정렬을 수행한다.

주요 단계는 다음과 같다:

1. 힙 구성(Heapify): 주어진 배열을 힙으로 변환한다.
   • 주어진 배열을 힙(Heap) 구조로 변환
   • Heapify 연산을 수행하여 최대 힙(또는 최소 힙) 구성
2. 정렬: 힙에서 원소를 하나씩 제거하여 정렬된 배열을 구성한다.
   • 루트(최댓값 또는 최솟값)를 제거하고, 힙을 재정렬
   • 반복적으로 수행하여 정렬된 배열 생성

힙 정렬 과정 예제

정렬할 배열:

1

[4, 10, 3, 5, 1]

1. 최대 힙(Max Heap) 구성

   1 2 3 4 5

   10 / \ 5 3 / \ 4 1

2. 루트(최대값 10)를 제거하고 배열 끝으로 이동

   1 2 3 4 5

   5 / \ 4 3 / 1

   → 정렬된 배열: [10]

3. Heapify 수행 후 최대 힙 유지

   1 2 3 4 5

   5 / \ 4 3 / 1

4. 다시 루트(최대값 5)를 제거하고 배열 끝으로 이동

   1 2 3

   4 / \ 1 3

   → 정렬된 배열: [5, 10]

5. 반복 수행하여 전체 정렬 완료

   1	[1, 3, 4, 5, 10]

결과적으로 오름차순 정렬이 수행됨

최대 힙 구성 과정

1. 초기 배열: [4, 10, 3, 5, 1]
2. 마지막 비단말 노드(인덱스 1, 값 10)부터 시작:
   • 인덱스 1은 이미 최대 힙 속성을 만족
3. 인덱스 0(값 4)에 대한 heapify:
   • 자식 노드들과 비교하여 최댓값(10)을 찾음
   • 4와 10을 교환: [10, 4, 3, 5, 1]
   • 인덱스 1에 대해 heapify 재귀 호출:
     • 자식 노드들과 비교하여 최댓값(5)을 찾음
     • 4와 5를 교환: [10, 5, 3, 4, 1]
       최종 최대 힙: [10, 5, 3, 4, 1]

정렬 과정

1. 루트(10)와 마지막 요소(1) 교환: [1, 5, 3, 4, 10]
   • 힙 크기를 4로 줄이고 heapify 수행
   • 결과: [5, 4, 3, 1 | 10] (막대는 힙과 정렬된 부분의 경계)
2. 루트(5)와 마지막 요소(1) 교환: [1, 4, 3, 5 | 10]
   • 힙 크기를 3으로 줄이고 heapify 수행
   • 결과: [4, 1, 3 | 5, 10]
3. 루트(4)와 마지막 요소(3) 교환: [3, 1, 4 | 5, 10]
   • 힙 크기를 2로 줄이고 heapify 수행
   • 결과: [3, 1 | 4, 5, 10]
4. 루트(3)와 마지막 요소(1) 교환: [1, 3 | 4, 5, 10]
   • 힙 크기를 1로 줄이면 정렬 완료

최대 힙을 이용한 오름차순 정렬

1. 배열을 최대 힙으로 구성한다.
2. 루트(최댓값)를 배열의 마지막 요소와 교환한다.
3. 힙의 크기를 1 감소시키고 루트에서 힙 속성을 복구한다(heapify).
4. 힙의 크기가 1이 될 때까지 2~3 단계를 반복한다.

최소 힙을 이용한 내림차순 정렬

1. 배열을 최소 힙으로 구성한다.
2. 루트(최솟값)를 배열의 마지막 요소와 교환한다.
3. 힙의 크기를 1 감소시키고 루트에서 힙 속성을 복구한다.
4. 힙의 크기가 1이 될 때까지 2~3 단계를 반복한다.

힙 정렬 알고리즘의 구현

파이썬으로 구현한 힙 정렬

 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

def heapify(arr, n, i):
    """
    주어진 배열 arr에서 인덱스 i를 루트로 하는 부분 트리를 최대 힙으로 만듭니다.
    n은 배열의 크기입니다.
    """
    # 여기서 `i`는 현재 검사 중인 루트 노드의 인덱스이다. 
    # 이진 트리에서 노드 `i`의 자식 노드들은 
    # 배열에서 `2*i+1`(왼쪽)과 `2*i+2`(오른쪽) 위치에 저장된다. 
    largest = i  # 루트를 가장 큰 값으로 초기화
    left = 2 * i + 1  # 왼쪽 자식
    right = 2 * i + 2  # 오른쪽 자식
    
    # 왼쪽 자식이 루트보다 크면 largest 갱신
    # 왼쪽 자식이 배열 범위 내에 있는지(`left < n`) 확인하고,
    # 그 값이 현재 `largest`보다 큰지 확인합니다.
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # 오른쪽 자식이 현재까지의 largest보다 크면 갱신
    # 오른 자식이 배열 범위 내에 있는지(`right < n`) 확인하고,
    # 그 값이 현재 `largest`보다 큰지 확인합니다.
    if right < n and arr[right] > arr[largest]:
        largest = right
    # 이 과정을 통해 루트, 왼쪽 자식, 오른쪽 자식 중에서 가장 큰 값의 인덱스를 `largest`에 저장한다. 
    
    # largest가 루트가 아니면 교환하고 재귀적으로 heapify 호출
    # 만약 `largest`가 현재 루트 `i`와 다르다면, 최대 힙 속성을 만족시키기 위해 두 값을 교환한다. 
    # 교환 후, 교환된 위치(이전 `largest` 위치)에서 다시 `heapify`를 호출한다. 
    # 이는 교환으로 인해 해당 위치에서 최대 힙 속성이 깨졌을 수 있기 때문이다. 
    # 이 재귀 과정은 리프 노드(자식이 없는 노드)에 도달하거나 최대 힙 속성이 만족될 때까지 계속된다.
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    """
    힙 정렬을 사용하여 배열을 정렬합니다.
    """
    n = len(arr)
    
    # 배열을 최대 힙으로 구성
    # 마지막 비단말 노드부터 루트까지 거꾸로 진행
    # 힙 정렬의 첫 단계는 주어진 배열을 최대 힙으로 변환하는 것.
    # 리프 노드는 자식이 없으므로 이미 최대 힙 속성을 만족한다. 
    # 따라서 마지막 비단말 노드(인덱스 `n//2-1`)부터 시작하여 루트(인덱스 0)까지 거꾸로 진행하며 각 노드에 대해 `heapify`를 수행한다. 
    # 이 과정은 상향식(bottom-up) 접근법으로, 각 서브트리를 최대 힙으로 만들어 최종적으로 전체 트리를 최대 힙으로 변환한다. 
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

	# 힙이 구성된 후, 최대 힙의 루트는 항상 배열의 최댓값.
	# 루트(인덱스 0)와 현재 힙의 마지막 요소(인덱스 `i`)를 교환하면, 최댓값이 배열의 올바른 정렬 위치로 이동한다. 
	# 교환 후에는 마지막 요소(이제 정렬됨)를 제외한 나머지 부분에 대해 다시 `heapify`를 수행하여 최대 힙 속성을 복원한다. 
	# 이 과정을 배열의 모든 요소에 대해 반복하면, 배열이 오름차순으로 정렬된다.
    # 힙에서 요소를 하나씩 추출
    for i in range(n - 1, 0, -1):
        # 현재 루트(최댓값)를 마지막 요소와 교환
        arr[i], arr[0] = arr[0], arr[i]
        
        # 크기가 줄어든 힙에 대해 heapify 수행
        heapify(arr, i, 0)
    
    return arr

자바스크립트로 구현한 힙 정렬

 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
30
31
32
33
34
35
36
37
38
39
40
41

function heapify(arr, n, i) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    
    // 왼쪽 자식이 루트보다 크면 largest 갱신
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    // 오른쪽 자식이 현재까지의 largest보다 크면 갱신
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    // largest가 루트가 아니면 교환하고 재귀적으로 heapify 호출
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

function heapSort(arr) {
    const n = arr.length;
    
    // 배열을 최대 힙으로 구성
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 힙에서 요소를 하나씩 추출
    for (let i = n - 1; i > 0; i--) {
        // 현재 루트(최댓값)를 마지막 요소와 교환
        [arr[0], arr[i]] = [arr[i], arr[0]];
        
        // 크기가 줄어든 힙에 대해 heapify 수행
        heapify(arr, i, 0);
    }
    
    return arr;
}

힙 정렬의 성능 분석

1. 시간 복잡도

   • 힙 구성(Build Heap): O(n) (일반적으로 O(n log n)으로 생각할 수 있지만, 더 정확한 상한은 O(n)입니다)
   • 정렬 과정: O(n log n)
   • 전체 시간 복잡도: O(n log n)
     힙 정렬의 시간 복잡도는 입력 배열의 초기 상태와 관계없이 항상 O(n log n)이다.
     이는 최선, 평균, 최악의 경우 모두 동일하다.

2. 공간 복잡도
   힙 정렬은 추가 배열 없이 입력 배열 내에서 정렬을 수행하므로 공간 복잡도는 O(1)이다.
   재귀 호출로 인한 스택 공간을 고려하면 최악의 경우 O(log n)이 될 수 있다.

3. 안정성
   힙 정렬은 불안정(unstable) 정렬 알고리즘이다.
   동일한 값을 가진 요소들의 상대적 순서가 정렬 과정에서 바뀔 수 있다. 이는 힙을 구성하는 과정과 요소를 추출하는 과정에서 발생할 수 있다.

힙 정렬의 최적화 기법

1. 반복적 Heapify
   재귀 대신 반복문을 사용하여 heapify를 구현하면 스택 오버플로우를 방지하고 성능을 향상시킬 수 있다.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   def heapify_iterative(arr, n, i): while True: largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest == i: break arr[i], arr[largest] = arr[largest], arr[i] i = largest

2. 병렬 처리
   힙 정렬의 일부 단계(특히 초기 힙 구성)는 병렬화가 가능하여 다중 코어 환경에서 성능을 향상시킬 수 있다.

3. 캐시 최적화
   메모리 액세스 패턴을 개선하여 캐시 효율성을 높이는 방법도 있다. 배열 요소 간의 간격을 줄이거나 지역성(locality)을 높이는 기법이 활용된다.

힙 정렬의 응용 분야

1. K 개의 가장 큰/작은 요소 찾기
   힙 자료구조를 활용하면 대용량 데이터에서 상위 K개 요소를 효율적으로 찾을 수 있다.
   이는 빅데이터 처리, 데이터 마이닝 등에서 유용하게 활용된다.

   1 2 3 4 5 6 7 8 9 10 11 12 13

   def find_k_largest(arr, k): # 최소 힙으로 k개 요소 유지 import heapq min_heap = [] for num in arr: if len(min_heap) < k: heapq.heappush(min_heap, num) elif num > min_heap[0]: heapq.heappop(min_heap) heapq.heappush(min_heap, num) return min_heap

2. 우선순위 큐 구현
   힙은 우선순위 큐를 구현하는 데 가장 적합한 자료구조이다. 이를 활용한 응용 프로그램으로는 다음과 같은 것들이 있다:

   • 다익스트라 알고리즘: 최단 경로 찾기
   • 프림 알고리즘: 최소 신장 트리 구성
   • 허프만 코딩: 데이터 압축
   • 작업 스케줄링: 우선순위에 따른 작업 할당

3. 외부 정렬
   대용량 데이터를 메모리에 모두 로드할 수 없을 때 사용하는 외부 정렬에서도 힙 정렬이 활용된다.
   여러 파일에서 데이터를 병합할 때 우선순위 큐로 힙을 사용하는 방식이다.

힙 정렬의 변형

1. 스무시 정렬(Smoothsort)
   힙 정렬의 변형으로, 이미 정렬된 데이터에 대해 O(n) 시간 복잡도를 가지도록 최적화된 알고리즘이다.
   레오나르도 수를 기반으로 한 특수한 힙 구조를 사용한다.

2. 인트로 정렬(Introsort)
   퀵 정렬, 힙 정렬, 삽입 정렬을 혼합한 하이브리드 정렬 알고리즘이다.
   퀵 정렬의 파티션 깊이가 너무 깊어지면 힙 정렬로 전환하여 최악의 경우 성능을 보장한다.

3. 제자리 병합 정렬(In-place Merge Sort)
   힙을 사용하여 병합 정렬을 제자리(in-place)에서 수행하는 방식으로, 추가 메모리 사용을 최소화한다.

참고 및 출처