#06 힙 정렬(Heap Sort)

2021.12.31 - [Comuter Science/Data Structure] - 힙 자료구조

힙 자료구조

 

힙 자료구조는 트리를 기반으로 설계된 자료구조이다.

힙 정렬은 어떤 max 값을 꺼내고 다시 정렬하는 데에 O(logn)의 시간 복잡도가 소요된다.

이를 활용해서 n개의 원소를 매번 logn을 통해 불러오므로 O(nlogn)의 시간이 소요되는 정렬 알고리즘이다.

 

1. 주어진 배열을 최대 힙으로 만든다(heapify)

2. n번만큼 반복하며 루트 노드와 맨 끝 노드를 바꾼 후에 heapify 연산을 통해 다시 힙으로 구현

https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm

최대 힙인 상태에서 root 노드를 가장 끝에 있는 리프노드와 변경하여 빼내는 모습

 

def heapify(arr, index, heap_size):
    largest = index
    left, right = index*2 +1 , index*2 + 2
    if left < heap_size and arr[largest] < arr[left]:
        # left 자식노드가 heap의 범위를 넘어가지 않고, 부모노드보다 크면 변경
        largest = left
    if right < heap_size and arr[largest] < arr[right]:
        # 마찬가지로 가장 큰 값을 가진 노드인지 확인
        largest = right
    if largest != index: # 인덱스 값이 변경되었으면 -> 자식노드중에 큰 값이 있다는 것
        arr[largest], arr[index] = arr[index], arr[largest]
        heapify(arr, largest, heap_size) # 변경 되었으므로 그 아래도 힙성질을 만족하는지 확인

def heap_sort(arr):
    n = len(arr)
    
    # max heap 만들기
    for i in range(n//2 -1, -1, -1): # 힙 성질에 따라 맨 끝 노드의 부모 노드는 n//2 -1 이다.
        heapify(arr, i, n)
    
    for i in range(n-1, -1, -1): # 인덱스 기준이므로 n-1이 가장 끝 인덱스
        arr[0], arr[i] = arr[i], arr[0] # 루트노드와 현 상태 가장 끝 노드 값 변경
        heapify(arr, 0, i) # 변경한 루트노드 값부터 다시 heap 만족하도록

수행 시간 비교

heap sort가 다른 nlogn 알고리즘 비해 좀 걸리긴 한다