Heap 정렬(Heap Sort) - Heap 정렬하기

이 글은 저번에 적었던 글에 이어서 진행됩니다.

2022.12.10 - [개념 정리/알고리즘] - Heap 정렬(Heap Sort) - Heap 만들기

Heap 정렬(Heap Sort) - Heap 만들기

Heap 정렬하기

Heap을 정렬하는 단계에서는 아래와 같은 과정을 거치게 됩니다.

1. heap에서 최댓값(max heap인 경우) 또는 최솟값(min heap인 경우) 제거 => 루트 노드 제거
2. heap의 가장 마지막 원소를 root 노드로 복사
3. root 노드에서부터 fixHeap 수행
4. 마지막 원소가 있었던 자리에 지웠던 최댓값(최솟값) 작성

저번 글에서 만든 max heap을 가지고 정렬을 해봅시다.

초기 max heap

먼저 루트 노드인 7을 제거하고 마지막 노드인 5를 루트 노드에 씁니다.

7 삭제, 5를 루트 노드에 복사

그리고 루트 노드에서부터 fixHeap 과정을 거칩니다. fixHeap의 자세한 과정은 위에 링크된 글을 참고하시면 됩니다. 단 여기서 주의할 점이 있습니다. 저번 글에 있는 코드에서 fixHeap을 호출할 때, 세 가지의 파라미터를 줬었습니다.

void fixHeap(int idx, int key, int numNodes)
{
 /*
 idx: 노드의 인덱스
 key: 노드의 값
 numNodes: 트리에 있는 노드의 수
 */
}

여기서 numNodes의 값은 현재 트리의 노드의 개수 - 1을 넘겨줘야 합니다. 지금 같은 상황에서는 numNodes 값으로 6이 아닌, 5를 줘야 합니다. 저희는 7을 제거했기 때문입니다.

fixHeap이 끝나면 아래와 같게 바뀝니다.

fixHeap 결과

그다음, 삭제했던 7을 5의 원래 위치에 넣어줍니다.

이를 배열로 표현하면 {0, 6, 3, 5, 1, 2, 7}로 가장 큰 값인 7이 가장 뒤로 간 것을 확인할 수 있습니다.

 

다음은 6을 제거하고 마지막 노드인 2를 루트 노드에 씁니다.

6 삭제, 2를 루트 노드에 복사

여기서도 같은 과정을 거치면 결과는 아래와 같습니다. (이 때는 numNodes의 값이 5 - 1 = 4가 되어야 합니다.)

이 상황도 배열로 표현하면 {0, 5, 3, 2, 1, 6, 7}로 6과 7이 잘 정렬되었음을 확인할 수 있습니다. 이를 연속적으로 하면 최종적으로 오름차순으로 정렬된 배열을 얻을 수 있게 됩니다.

최종 정렬 결과

이를 c++ 코드로 표현하면 아래와 같습니다.

void heapSort(int numNodes)
{
    /*
      numNodes: 트리에 있는 노드의 개수
      input: 사용자가 입력으로 준 배열(정렬해야 하는 배열)
    */
    
    // Construct Max Heap
    for (int i = numNodes / 2; i >= 1; i--) { fixHeap(i, input[i], numNodes); }
    
    // Sorting
    for (int i = numNodes; i > 1; i--)
    {
        int maxKey = input[1]; int lastKey = input[i];
        fixHeap(1, lastKey, i - 1);
        input[i] = maxKey;
    }
}

오름차순이 아닌 내림차순으로 정렬하고 싶으시다면 heap을 구성할 때 min heap으로 구성한 후, fixHeap에서 반대로 수정하면 내림차순으로 정렬된 배열을 얻을 수 있습니다.

Heap sort에서의 Time Complexity

트리에 있는 노드의 개수를 N이라고 합시다.

처음 삭제가 일어날 때, fixHeap에서 2 * \(log_{2} N \)만큼 소요됩니다.

두 번째 삭제가 일어날 때, fixHeap에서 2 * \(log_{2} \left( N - 1 \right) \)만큼 소요됩니다.

세 번째 삭제가 일어날 때, fixHeap에서 2 * \(log_{2} \left( N - 2 \right) \)만큼 소요됩니다.

따라서 모든 삭제와 fixHeap이 끝날 때 소요된 시간들을 합치면 아래의 수식으로 표현할 수 있습니다.

$$ 2 * \sum_{i=1}^N \lfloor log_{2} i \rfloor $$

이 식을 풀면 최종적으로 \( 2 * log_{2} \left( N! \right) \) 이 됩니다. 그리고 이 식은 Stirling's Approximation에 의해 \( Nlog_{2} N - N + O(log_{2} N) \) 로 바뀝니다.(https://iq.opengenus.org/time-complexity-of-heap-sort/)

Big-O notation에 의해 time complexity는 O(n * logn) 입니다.