Algorithm - Heap Sort

Heap Sort

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

 

구현

• 최대 힙 : 부모노드가 자식 노드보다 큰 트리
• 최소 힙 : 부모노드가 자식 노드보다 작은 트리
• 처음에 완전 이진트리를 기본으로 하는 최대 힙의 구조를 구현함
• 구현된 힙의 루트 요소를 마지막으로 보낸 후 다시 최대 힙을 구하는 heapify과정을 반복
• heapify는 왼쪽 인덱스와 오른쪽 인덱스의 값을 비교하여 큰 값과 교체하는 방식을 재귀적으로 반복하는 함수

def heapify(arr, idx, n):
    Max = idx
    left_idx = 2 * idx + 1
    right_idx = 2 * idx + 2
    if left_idx < n and arr[left_idx] > arr[Max]:
        Max = left_idx
    if right_idx < n and arr[right_idx] > arr[Max]:
        Max = right_idx
    if Max != idx:
        arr[idx], arr[Max] = arr[Max], arr[idx]
        heapify(arr, Max, n)

def heapSort(arr):
    # 이진 트리의 성질에 의해 최초 힙 구성시 배열의 중간부터 시작하면 모든 요소를 다 비교할 수 있음 
    for i in range(len(arr) // 2 - 1, -1, -1):
        heapify(arr, i, len(arr))
    
    # 최대 힙의 루트 요소를 맨 뒤로 보낸 후 다시 최대 힙을 구성하는 것을 반복
    for i in range(len(arr) - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i)
    return arr

 

공간 복잡도

각 요소의 값의 교환으로 인해 추가적으로 메모리를 사용하지 않기 때문에 O(1)

 

시간 복잡도

힙 트리의 전체 depth가 거의 log2n이므로 O(logn)의 시간이 필요하고,

요소의 모든 값을 고려해야하므로 O(n)의 시간이 소요되므로 O(nlogn)

 

장점

• 시간복잡도가 좋은 편임(O(nlogn))
• 가장 큰 값이나 작은 값을 구할 때 한 번의 힙 구성을 통해 구하는 것이 가능

 

단점

• 실제 시간을 측정했을 때 퀵 정렬보다 느린 편