[알고리즘] 힙 정렬(Heap Sort)

힙 정렬이란 ?

• 힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다.
• 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리이다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 즉, 이러한 두 값의 대소 관계가 일정하면 된다.

• 완전 이진 트리란?
  • 노드를 삽입할 때 왼쪽부터 추가하는 이진트리(모든 노드의 차수가 2이하로 구성된 트리)

• 모든 부모와 자식 관계는 항상 부모의 값 >= 자식의 값 성립
• 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다. 따라서 힙은 형제의 대소관계가 정해져 있지 않으므로 부분 순서 트리(partical ordered tree)라고도 한다.
• 시간복잡도 - O(n log n) 
• 단순 선택 정렬의 시간 복잡도 O(n^2)

이러한 순서로 힙을 배열에 저장하면 부모 인덱스와 왼쪽 아래에 있는 자식(왼쪽 자식), 오른쪽 아래에 있는 자식(오른쪽 자식) 인덱스 사이에는 다음과 같은 관계 성립된다.

 

원소 a[i]에서

• 부모 : a[(i-1) // 2]
• 왼쪽 자식 : a[i * 2 + 1]
• 오른쪽 자식 : a[i * 2+ 2]

 

힙 정렬의 특징

 

힙에서 최댓값은 루트에 위치한다는 특징을 이용하여 정렬하는 알고리즘이다.

• 힙에서 최댓값인 루트를 꺼낸다.
• 루트 이외의 부분을 힙으로 만든다.

이 과정에서 꺼낸 값을 나열하면 정렬이 끝난 배열이 완성된다. 즉 힙 정렬은 선택 정렬을 응용한 알고리즘이다.

힙 정렬에서 최댓값인 루트를 꺼낸 뒤 다시 남은 원소 중에서 최댓값을 구해야 한다.

 

루트를 삭제한 힙의 재구성

 

1. 루트를 꺼낸다.
2. 마지막 원소(가장 하단의 오른쪽에 위치한 원소)를 루트로 이동한다.
3. 루트에서 시작하여 자신보다 값이 큰 자식과 자리를 바꾸고 아래쪽으로 내려가는 작업을 반복한다. 자식의 값이 작거나 리프의 위치에 도달하면 종료한다.

힙 삽입

 

힙 정렬 알고리즘

#최대 힙 형태로 구성
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

    #largest 값이 갱신되었다면 노드 교환, heapify 재귀
    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 range(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

if __name__ == "__main__":

    unsorted = [3,18,7,5,1,9,14,28]
    print(heap_sort(unsorted))