힙 정렬 (Heap Sort)

소개

• 모든 노드가 힙 속성 (각 노드의 값이 자신의 자식노드 값보다 크거나 [최대 힙] 작은 [최소 힙] 완전 이진 트리) 을 만족하도록 재귀적으로 트리 구조를 만들어 정렬한다.
• 추가적인 메모리를 필요로 하지 않으면서 항상 \(O(NlogN)\) 을 보장한다.
• 시간 복잡도가 \(O(NlogN)\) 이지만 실제로는 동일한 시간 복잡도를 가진 다른 정렬 알고리즘 (ex. Quick Sort) 보다 느리다.

 

 

힙 (Heap) vs 이진 탐색 트리 (Binary Search Tree)

• 공통점 : 완전 이진 트리로 구성된다.
• 차이점 :
  • 힙
    • 부모 노드가 자식 노드 보다 크거나 작은 속성을 만족한다. 각각 최대 힙과 최소 힙이라 부른다.
    • 정렬에 강점을 가지고 있다.
  • 이진 탐색 트리
    • 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 속성을 만족한다.
    • 탐색에 강점을 가지고 있다.

 

 

과정 (최소힙을 기준으로 작성)

• 삽입 (힙 구성)
  • 삽입하는 노드 위치는 항상 맨 마지막이다.

 

• 삭제 (실질적인 정렬 과정 - 정렬 후 Heapify를 반복)

 

 

코드

public static void Swap(int[] arr, int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

public static void Heapify(int[] arr, int parent, int size) {
    int temp_parent = parent;
    int left_child = parent * 2 + 1;
    int right_child = parent * 2 + 2;

    if (left_child < size && arr[temp_parent] > arr[left_child])
        temp_parent = left_child;

    if (right_child < size && arr[temp_parent] > arr[right_child])
        temp_parent = right_child;

    if (parent != temp_parent) {
        Swap(arr, parent, temp_parent);
        Heapify(arr, temp_parent, size);
    }
}

public static void main(String[] args) {
    int[] arr = new int[]{7, 3, 22, 6, 2, 14, 1};
    int len = arr.length;

    // i의 초기값은 배열의 제일 끝 자식노드의 부모노드부터 시작 (O(N)으로 수행)
    for (int i = len / 2 - 1; i >= 0; --i)
        Heapify(arr, i, len);

    for (int i = len - 1; i > 0; --i) {
        Swap(arr, 0, i);    // 루트 노드와 마지막 노드를 교환
        Heapify(arr, 0, i); // 루트 노드를 기준으로 다시 힙 속성을 만족하도록 구축
	}
}

 

 

결과

 

 

계산 복잡도

Time Complexity : \(O(N) \, + \, O(NlogN) \, = O(NlogN)\)

힙 구축 (삽입) - \(O(NlogN)\)

• 하지만, 이 과정을 \(O(N)\)에 수행 가능한 방법이 있다고 한다. URL

구축된 힙에서 하나씩 뽑으면서 정렬 - \(O(NlogN)\)

• Best : \(O(NlogN)\)
• Average : \(O(NlogN)\)
• Worst : \(O(NlogN)\)

Space Complexity : \(O(N)\) - 재귀로 호출되는 함수 스택이 N개