[알고리즘/정렬] 힙 정렬

0. 🔖 목차

1. 힙 정렬
   1-1 힙 정렬 개념
   1-2 알고리즘
   1-3 복잡도

1. 힙 정렬

1-1. 힙 정렬 개념

힙 자료구조를 이용한 정렬 방법이다.

최대 힙을 사용하면 오름차순으로, 최소 힙을 사용하면 내림차순으로 정렬할 수 있다.

힙 정렬의 과정은 아래와 같다.

1. 완전 이진 트리를 구성
2. 최대 힙으로 만듦(heapify)
3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환
4. 2와 3을 반복한다.

위 그림은 1, 2, 3번의 과정을 순차적으로 진행하는 그림이다.

위 그림의 과정을 반복하면 오름차순으로 정리된다.

1-2. 알고리즘

def heap_sort(arr):
    n = len(arr)
    # 배열을 힙으로 만들기
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 하나씩 원소를 추출해서 정렬
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 가장 큰 원소를 배열의 끝으로
        heapify(arr, i, 0)
    
    return arr

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    # 왼쪽 자식이 현재 원소보다 크면
    if left < n and arr[largest] < arr[left]:
        largest = left
    # 오른쪽 자식이 현재 원소보다 크면
    if right < n and arr[largest] < arr[right]:
        largest = right
    # 큰 값이 부모 위치에 있지 않으면
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 스왑
        # 스왑된 위치에서 다시 힙 속성을 유지하기 위해
        heapify(arr, n, largest)

1-3. 복잡도