정렬 알고리즘 - 힙 정렬(Heap Sort)

완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 알고리즘입니다.

힙은 큰 키(우선 순위)에 자주 액세스하거나 키(우선 순위) 중심으로 정렬된 시퀀스를 활용해야 할 때 유용한

자료구조입니다. 힙은 한 노드가 최대 두 개의 자식 노드를 가지면서, 마지막 레벨을 제외한 모든 레벨에서

노드들이 꽉 채워진 **완전 이진 트리(complete binary tree)**를 기본으로 합니다.

힙 속성(heap property)은 다음 두 가지입니다.

heap order property : 각 노드의 값은 자신의 자식노드가 가진 값보다 크거나 같다(최대 힙, Max heap).

각 노드의 값은 자신의 자식노드가 가진 값보다 작거나 같다(최소 힙, Min heap).

heap shape property : 모양은 완전 이진 트리이다. 즉 마지막 레벨의 모든 노드는 왼쪽에 쏠려 있다.

힙과 이진 탐색 트리(binary search tree) 모두 이진 트리라는 점에서 공통점을 가지만 노드값이 다소 다르게

구성돼 있는 점을 확인할 수 있습니다. 힙은 각 노드의 값이 자식노드보다 큰 반면, 이진 탐색 트리는 왼쪽 자식

노드가 제일 작고 부모노드가 그 다음 크며 오른쪽 자식노드가 가장 큰 값을 가집니다.

힙은 우선순위(키) 정렬에, 이진 탐색 트리는 탐색에 강점을 지닌 자료구조입니다.

힙은 1차원 배열(array)로도 표현이 가능합니다. 어떤 노드의 인덱스를 index, 왼쪽 자식노드의 인덱스를

left_index, 오른쪽 자식노드의 인덱스를 right _index로 선언하면 다음과 같은 관계를 지닙니다.

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

주어진 자료구조에서 힙 성질을 만족하도록 하는 연산을 heapify라고 합니다.

파이썬으로 구현하면 아래와 같습니다.

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)

heapfify는 최악의 경우 루트노드에서 리프노드까지 값을 비교해야 하므로 트리의 최대 높이(log⁡n)에

의존적입니다. 값을 비교하거나 바꾸는 연산은 O(1)이므로 결과적으로 O(log⁡n)이 됩니다.

1. 주어진 원소들로 최대 힙을 구성합니다(heapfify).
2. 최대 힙의 루트노드와 마지막 리프노드를 교환합니다.
3. 새 루트노드에 대해 최대 힙을 구성합니다.
4. 원소의 수만큼 해당 과정을 반복 수행합니다.

시간복잡도는 최초로 최대 힙을 만드는 시간복잡도는 O(n)입니다.

힙이 구성된 상태에서 각 노드에 대해 heapify를 수행하는 경우, 마지막 리프노드가 루트노드에 올라오기까지

트리의 높이(logn)만큼 자리 이동을 해야 합니다. 이렇게 heapify를 해야 하는 노드들이 n개가 있으므로

시간복잡도는 O(nlog⁡n)이 됩니다. 따라서 O(n)+O(nlog⁡n)이며 결과적으로 O(nlog⁡n)이 됩니다.

 

장점

• 시간 복잡도가 으로 빠른 편에 속합니다O(nlogn).
• 가장 큰 값을 구하거나 가장 작은 값을 구할 때 좋습니다.

단점

• 실제 프로그램에 구현할 경우 평균 계산 속도가 퀵 정렬보다 느리고 불안정합니다.

def heap_sort(arr):

    def heapify(arr, index, heap_size):
        largest = index
        left_index = 2 * index + 1
        right_index = 2 * index + 2

        if left_index < heap_size and arr[left_index] > arr[largest]:
            largest = left_index

        if right_index < heap_size and arr[right_index] > arr[largest]:
            largest = right_index

        if largest != index:
            arr[largest], arr[index] = arr[index], arr[largest]
            heapify(arr, largest, heap_size)

    n = len(arr)
    # BUILD-MAX-HEAP (A)
    # 인덱스 : (n을 2로 나눈 몫-1)~0
    # 최초 힙 구성시 배열의 중간부터 시작하면
    # 이진트리 성질에 의해 모든 요소값을
    # 서로 한번씩 비교할 수 있게 됨 : O(n)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, i, n)
    # Recurrent (B) : 2~4단계
    # 한번 힙이 구성되면 개별 노드는
    # 최악의 경우에도 트리의 높이(logn)
    # 만큼의 자리 이동을 하게 됨
    # 이런 노드들이 n개 있으므로 : O(nlogn)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i)
    return arr