[CLRS] [6-4] Heapsort (힙정렬)

0. Intro

- 우리는 6-2, 6-3 에서 max_heapify()와 build_max_heap()을 구현해보았다.

- 두 함수를 이용하여 배열을 정렬하는 알고리즘을 한번 구현해보자(Heapsort)

 

1. Heapsort?

- 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법을 의미함

- Heapsort의 알고리즘을 나타내면 다음과 같다.

 

i) 정렬해야할 n개의 데이터들을 Max-Heap을 만든다.

ii) root-node(최댓값을 가장 마지막 node와 바꾼다.

iii) 그 후 heap에서 pop()을 한 후 queue에 enqueue한다.

iv) 그 후 max_heapify()를 root_node에서 실행한다.

v) ii)~iv)까지를 계속 반복한다. (heap이 empty가 될 때까지)

 

- heapsort의 시간복잡도는 O(nlogn)이다.

- heapsort의 장점은 가장 큰 값을 찾아내고 싶을 때 되게 유용하다.

 

1.1.  과정을 그림으로

2. Code

- 이를 코드로 구현하면 다음과 같다. 

def max_heapify(arr,i):
    left_node = 2*i
    right_node = 2*i+1

    if (left_node <= len(arr)-1) and arr[left_node] > arr[i]:
        largest = left_node
    else:
        largest = i
    if (right_node <= len(arr)-1) and arr[right_node] > arr[largest]:
        largest = right_node

    if largest != i :
        arr[i],arr[largest] = arr[largest], arr[i]
        max_heapify(arr,largest)

 

def build_max_heap(arr):
    for i in range(((len(arr)-1)//2),0,-1):
        max_heapify(arr,i)

 

def heap_sort(arr):
    build_max_heap(arr)
    sorted_arr = deque()

    for i in range(len(arr)-1,0,-1):
        arr[1],arr[-1] = arr[-1],arr[1]
        sorted_arr.appendleft(arr.pop())
        max_heapify(arr,1)
    
    return sorted_arr

 

3. 예제

- A = <5,13,2,25,7,17,20,8,4> 를 heapsort 하시오

#input
arr = [0] + [5,13,2,25,7,17,20,8,4]

print(heap_sort(arr))

#output
deque([2, 4, 5, 7, 8, 13, 17, 20, 25])