힙 정렬 (Heap Sort)

힙 정렬

: 힙은 완전 이진트리의 구조를 갖고 있는데, 자식 노드의 값이 부모 노드의 값보다 클 수 없다(작거나 같아야 함)는 조건을 만족해야 한다. 

 

1. 최대 힙을 구성한다. (인덱스의 0번째 값이 최댓값이 된다)

2. 최댓값을 배열의 가장 마지막 위치에 놓는다. (큰 값을 뒤로 보내주는 과정 - 교환)

3. 그 다음 새로운 루트 노드에 대해 최대 힙을 수행한다.

4. 원소의 개수만큼 2~3번의 과정을 반복한다.

 

 

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

heapify에서는 left = index * 2 +1, right = index * 2 + 2 공식을 만족한다.

 

 

 

파이썬으로 구현한 힙 정렬

def heapify(arr, index, heap_size):
    largest = index
    left = index * 2 + 1 # 왼쪽 자노드
    right = index * 2 + 2 # 오른쪽 자노드
    # 왼쪽 자식이 현재 요소보다 크면 인덱스 교체!
    if left < heap_size and arr[left] > arr[largest]:
        largest = left
    # 오른쪽 자식이 현재 요소보다 크면 인덱스 교체!
    if right < heap_size and arr[right] > arr[largest]:
        largest = right
    # 교체된 적이 있다면 교체된 index와 largest 요소값 교체!
    if largest != index:
        arr[largest], arr[index] = arr[index], arr[largest]
        # 변경된 부분을 중심으로 다시 한번 heapify
        heapify(arr, largest, heap_size)

def heap_sort(arr):
    n = len(arr)

    # 최초 힙
    # 트리의 절반부터 거꾸로 올라가며 하는 것이 효율적
    for i in range(n // 2 -1, -1, -1):
        heapify(arr, i, n)
    # 한번 구성된 힙을 정렬
    # 가장 큰 값(루트) 을 가장 끝 값으로 이동한 후 힙 생성.
    for i in range(n-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i)
    return arr

arr = [5, 2, 3, 9, 6, 1, 8, 4, 7]
print(heap_sort(arr))