[Algorithm] 힙 정렬(Heap sort) 알고리즘

Heap sort

Idea

우선 heap의 개념부터 정리하겠습니다. 

Heap

완전 이진트리 형태이며, 최대 힙과 최소 힙으로 나뉜다. 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 완전 이진트리이고, 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리이다.
이러한 힙의 형태를 유지하면서 삽입과 삭제 연산이 가능하도록 해야하며, 이러한 연산을 heapify이라 한다.

ex) 최대 힙

힙과 이진 탐색 트리는 명확한 차이점을 가진다. 두 자료구조 모두 이진트리라는 점은 같지만, 노드 값이 다르게 구성된다.
이진 탐색 트리의 경우 가장 왼쪽의 리프노드가 가장 작고, 가장 오른쪽의 리프노드가 가장 큰 값을 가진다. 하지만 힙의 경우 부모와 자식 간의 값의 순서만 지키면 되기 때문에 차이점이 있다.

Heap 표현
heap을 구현하기 위해서 1차원 배열을 사용한다. 완전이진트리 형태이므로 다음이 성립한다.

left_index = 2 * index + 1
right_index = 2 * index + 2​

이를 기반으로 왼쪽의 heap을 오른쪽의 배열로 표현할 수 있다.

Heapify
heap의 성질을 유지시키는 연산이다. 이를 구현하면 아래와 같다.

더이상 교체가 일어나지 않을 때까지 재귀적으로 호출

해당 연산의 time complexity는 O(logn) 이다.

def heapify(unsorted, index, heap_size):

    largest = index
    left_index = 2 * index + 1
    right_index = 2 * index + 2
    
    if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
        largest = left_index
        
    if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
        largest = right_index
        
    if largest != index:
        unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
        heapify(unsorted, largest, heap_size)​

 

 

이제 heap sort 과정을 살펴보겠습니다.

1. 주어진 unsorted 배열을 통해 최대 힙을 구성한다.
2. 최대 힙의 루트 노드(첫번째 요소)와 말단 노드(마지막 요소)를 교환한다.
3. 새 루트 노드에 대해서 다시 최대 힙을 구성한다.
4. 주어진 배열의 원소 개수만큼 2, 3을 반복한다.

이를 구현하면 아래와 같습니다.

Code

def heap_sort(unsorted):
    n = len(unsorted)
    
    # 최대 힙 구성 : O(n)
    for i in range(n // 2 - 1, -1, -1):
        heapify(unsorted, i, n)
        
    # 트리의 높이(logn)만큼의 자리 이동 -> n번 반복 : O(nlogn)
    for i in range(n - 1, 0, -1):
        unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
        heapify(unsorted, 0, i)
    return unsorted

 

Time complexity

위 코드를 살펴보면, 크게 두가지로 동작을 나눌 수 있습니다.

1.  최대 힙을 만드는 과정 -> O(n)
2. 루트 노드와 말단 노드를 교환하고, heapify 연산 수행 -> n* O(logn) = O(nlogn)

따라서 최종적인 시간 복잡도는 O(n) + O(nlogn) = O(nlogn) 입니다.