[알고리즘] 파이썬으로 힙 정렬 구현하기 :: heap sort in python

파이썬으로 힙 정렬(heap sort) 구현하기

힙 정렬(Heap sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

본 포스팅에서는 최소힙으로 오름차순 정렬을 구현해보겠다.

내림차순은 아래 코드에서 부등호방향만 반대로 바꾸면 된다.

def heapify(li, idx, n):
    l = idx * 2;
    r = idx * 2 + 1
    s_idx = idx
    if (l <= n and li[s_idx] > li[l]):
        s_idx = l
    if (r <= n and li[s_idx] > li[r]):
        s_idx = r
    if s_idx != idx:
        li[idx], li[s_idx] = li[s_idx], li[idx]
        return heapify(li, s_idx, n)
 
def heap_sort(v) :
    n = len(v)
    v = [0]+v
 
    # min heap 생성
    for i in range(n, 0, -1) :
        heapify(v, i, n)
 
    # min element extract & heap
    for i in range(n, 0, -1) :
        print(v[1])
        v[i], v[1] = v[1], v[i]
        heapify(v, 1, i-1)
 
heap_sort([5,3,4,2,1])

* index를 편하게 하기 위해 1번째자리부터 시작한다. (v[0]에 0을 넣은 이유)

* heapify() 예시

> v = [0,5,3,4,2,1] # 0 : index를 1부터 시작하기 위해 추가

> heapify(v, 1, len(v)-1)

> print(v)

[0, 3, 1, 4, 2, 5]

idx = 1 일 때, 1번 째 노드의 왼쪽 자식은 2에 위치하는 3이고, 오른쪽 자식은 3에 위치하는 4이다.

3과 4중 3이 더 작기 때문에 s_idx는 2가 되고, 따라서 첫 번째 노드와 두 번째 노드의 위치가 바뀐다.

이후, 다시 heapify(v, s_idx, len(v)-1) 재귀함수가 실행된다.

즉, 

> v = [0,3,5,4,2,1]

> heapify(v, 2, len(v)-1) 

과 같은 함수가 실행된다.

따라서 최종 결과는 다음과 같다.

* heap_sort() 예시

> for i in range(n, 0, -1) :

heapify(v, i, n)

[0, 1, 2, 4, 5, 3]

에서 min heap이 생성된다.

[i = 5, i = 4, i = 3 일 때]

[i = 2 일 때]

[i = 1 일 때]

Min Heap이 완성 되었으면, 첫 번째 노드부터 출력하면서 Heap을 재정의한다.

> for i in range(n, 0, -1) :

print(v[1]) # heap에서 최소값부터 출력

v[i], v[1] = v[1], v[i] # 최소값 제거 후 heap 재정의

heapify(v 1, i-1)

i = n 일 때를 예를들면, 다음과 같이 Min Heap 상태에서

가장 위의 첫 번째 노드가 출력되고,

가장 leaf 노드가 첫 번째 노드로 옮긴 후, heapify() 함수가 실행되어 Heap을 재정의한다.

위 과정이 반복되어 오름차순 정렬이 끝난다.