완전 이진 트리를 기본으로 하는 힙(Heap) 자료 구조를 기반으로한 정렬 방식

완전 이진 트리란?

삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리

시간복잡도

과정

1. 최대 힙을 구성
2. 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임
3. 힙의 사이즈가 1보다 크면 위 과정 반복
   

루트를 마지막 노드로 대체 (11 -> 4), 다시 최대 힙 구성

이와 같은 방식으로 최대 값을 하나씩 뽑아내면서 정렬하는 것이 힙 소트입니다.

heapify

최대 힙에서 마지막 값과 교환한 이후에 다시 최대 힙을 구성하는 작업이 필요합니다. 이러한 과정을 heapify 라고 부릅니다.
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) 

최종 코드

최대 힙에서 루트의 값을 추출하고 정렬하는 힙 정렬의 코드는 다음과 같습니다.

def heap_sort(unsorted):
	n = len(unsorted)
    for i in rnage(n//2 - 1, -1, -1):
    	heapify(unsorted, i, n)
    for i in range(n - 1, 0, -1):
    	unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
        heapify(unsorted, 0, i)
    return unsorted