[알고리즘] Heap Sort

Heap Sort

최대 힙, 최소 힙 구조를 통해 정렬하는 알고리즘

---

Heap 이란?

최솟값이나 최댓값을 빠르게 찾아내기 위해 사용되는 구조로
완전 이진 트리를 기반으로 하는 트리이다

각 노드의 값이 자신의 자식노드가 가진 값보다 크거나 같다면 최대 힙 (Max Heap)
각 노드의 값이 자신의 자식노드가 가진 값보다 작거나 같다면 최소 힙 (Min Heap)

---

Process

1. 완전 이진트리 형태의 최대 힙을 만든다

2. 힙에서 하나씩 데이터를 꺼내어 배열의 맨 뒤에 저장한다

    이 때 최댓값부터 꺼내지므로 내림차순으로 정렬된다

3. 남겨진 데이터는 최대 힙을 유지한다

---

heapify

힙 성질을 만족하도록 하는 연산을 heapify 라고 한다

 

예를 들어 최대 힙의 경우

루트 노드부터 리프 노드까지 부모 노드가 자식 노드보다 값이 크다는 최대 힙의 성질을 만족하도록 하는 연산이다

---

Code

array = [2, 3, 4, 10, 8, 1, 6, 9, 5]
n = len(array)

def heapify(idx, n):
    parent = idx
    left = 2 * idx + 1
    right = 2 * idx + 2

    if left < n and array[left] > array[parent]:
        parent = left

    if right < n and array[right] > array[parent]:
        parent = right

    if parent != idx:
        array[parent], array[idx] = array[idx], array[parent]
        heapify(parent, n)


def heapSort():
    # 최대 힙 구성
    for i in range(n//2, -1, -1):
        heapify(i, n)

    # 최대 값을 배열뒤로 보내 정렬
    for i in range(n-1, 0, -1):
        array[0], array[i] = array[i], array[0]
        heapify(0, i)


heapSort()
print(array)

---

Time Complexity

힙 트리는 완전 이진 트리이므로 전체 높이가 log₂N 이다

따라서 데이터 하나를 삽입하거나 삭제 할 때의 재정비 시간이 log₂N 만큼 소요된다

데이터 개수가 n개 이므로 O(Nlog₂N) 의 시간이 걸린다

 

Quick, Merge Sort와 평균 시간복잡도는 동일하지만 실제로 둘이 Heap Sort 보다 더 빠르다고 한다

---

Space Complexity

정렬하고자하는 배열안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다 (in-place sorting)

따라서 O(N) 이다

---

Heap 자료구조는 삭제 시 말단 노드가 루트자리로 swap 되며 같은 값을 가진 데이터의 위치가 변경될 수 있어 unstable sorting 이다