[알고리즘] 파이썬으로 힙정렬(Heap sort) 구현하기 | Python

힙정렬(Heap Sort)은 힙 트리(Heap Tree)를 구성해 정렬하는 방법으로, 앞서 설명했던 병합정렬이나 퀵정렬만큼 빠른 정렬 알고리즘이다. 내림차순 정렬을 위해서는 최대힙을 구성하고 오름차순 정렬을 위해서는 최소힙을 구성해야 한다. 힙을 통해 정렬하는 만큼 힙에 대한 이해가 선행되어야 한다.

 

힙: 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리의 자료구조

최대힙: 부모노드의 키값이 자식노드의 키값보다 항상 큰 경우

최소힙: 부모노드의 키값이 자식노드의 키값보다 항상 작은 경우

 

힙생성 알고리즘은 특정 노드의 두 자식 중 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다. 

 

array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]

# 1. 상향식: 특정 노드를 기준으로 위로 올라감
def heap_sort(array):
    n = len(array)
    # heap 구성
    for i in range(n):
        c = i
        while c != 0:
            r = (c-1)//2
            if (array[r] < array[c]):
                array[r], array[c] = array[c], array[r]
            c = r
            print(array)
    # 크기를 줄여가면서 heap 구성
    for j in range(n-1, -1, -1):
        array[0] , array[j] = array[j], array[0]
        r = 0
        c = 1
        while c<j:
            c = 2*r +1
            # 자식 중 더 큰 값 찾기
            if (c<j-1) and (array[c] < array[c+1]):
                c += 1
            # 루트보다 자식이 크다면 교환
            if (c<j) and (array[r] < array[c]):
                array[r], array[c] = array[c], array[r]
            r=c
            print(array)
    print(array)
heap_sort(array)

위 코드를 구현하면, 아래와 같이 잘 나오는 것을 확인할 수 있다.

 

 

 

참고자료:

힙 정렬 - 위키백과, 우리 모두의 백과사전

 

10. 힙 정렬(Heap Sort)

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전