힙 정렬

개념

 

힙 정렬(heap sort)은 힙의 특성을 이용하여 정렬하는 알고리즘이다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리이다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 즉, 두 값의 대소 관계가 일정하면 된다.

힙에서 부모와 자식 관계는 일정하지만 형제(sibling)사이의 대소 관계는 일정하지 않다. 

 

 

위의 사진은 힙의 원소를 배열에 어떻게 저장할 것인지를 나타낸다. 먼저 가장 위쪽에 있는 루트(10)를 저장하고, 한 단계 아래에서 왼쪽부터 배열의 인덱스 값을 1씩 증가시키면서 각 원소를 저장한다. 가장 마지막에 있는 원소 1까지 반복하여 힙을 배열에 저장하면 완료된다.

 

이러한 순서로 힙을 배열에 저장하면 다음과 같은 부모 인덱스와 왼쪽, 오른쪽 자식간에 다음과 같은 관계가 성립한다.

원소 a[i]에서 -  부모 : a[(i - 1) // 2] -  왼쪽 자식 : a[i * 2 + 1] -  오른쪽 자식 : a[i * 2 + 2]

 

 

특징

 

힙 정렬은 '힙에서 최댓값은 루트에 위치한다'는 특징을 이용하여 정렬하는 알고리즘이다. 다음과 같은 작업을 반복한다.

-  힙에서 최댓값인 루트를 꺼낸다.

-  루트 이외의 부분을 힙으로 만든다.

 

이 과정에서 꺼낸 값을 나열하면 정렬이 끝난 배열이 완성된다. 즉, 힙 정렬은 선택 정렬을 응용한 알고리즘이다.

또한 힙 정렬에서 최댓값인 루트를 꺼낸 뒤 다시 남은 원소 중에서 최댓값을 구해야 한다. (남은 원소로 구성한 트리도 힙이 되도록 재구성)

 

 

 

루트를 삭제한 힙의 재구성

 

 

루트를 삭제하고 다시 힙으로 만들기 위해 원소를 알맞은 위치로 이동하는 순서는 다음과 같다.

 

1. 루트를 꺼낸다.

2. 마지막 원소(가장 하단의 오른쪽에 위치한)를 루트로 이동한다.

3. 루트에서 시작하여 자신보다 값이 큰 자식과 자리를 바꾸고 아래쪽으로 내려가는 작업을 반복한다. 자식의 값이 작거나 리프의 위치에 도달하면 종료한다.

 

힙 정렬 알고리즘의 흐름을 이해해본다면 (n값은 배열의 원소 수, i값은 배열의 마지막 인덱스)

1. i값을 n - 1로 초기화

2. a[0]과 a[i]를 교환

3. a[0], a[1] ,,,, a[i - 1]을 힙으로 만든다.4. i값을 1씩 감소시켜 0이 되면 종료한다. 그렇지 않으면 2로 돌아간다.

 

 

배열을 힙으로 만들기

 

 

위 그림과 같은 이진 트리가 있다고 가정하자. 루트가 4인 서브트리 A는 힙이 아니다. 그러나 4의 왼쪽 자식과 오른쪽 자식을 루트로 하는 서브트리 B와 C는 모두 힙 상태이다. 루트를 삭제한 힙을 재구성하려면 마지막 원소를 루트로 이동시켜 알맞은 위치까지 아래로 옮겨야 한다. 즉, 루트 4를 알맞은 위치까지 아래로 옮기면 서브트리 A를 힙으로 만들 수 있다.

 

이 방법을 사용하면 가장 아랫부분의 작은 서브트리부터 상향식(bottom up)으로 진행하여 전체 배열을 힙으로 만들 수 있다. 가장 아랫부분의 오른쪽 서브트리의 힙을 만들고, 왼쪽 서브트리로 진행한다. 그 단계를 완료하면 한 단계 위로 이동하면서 각각의 서브트리를 힙으로 만든다. 

 

 

<code>

# [Do it! 실습 6-16] 힙 정렬 알고리즘 구현하기

from typing import MutableSequence

def heap_sort(a: MutableSequence) -> None:
    """힙 정렬"""

    def down_heap(a: MutableSequence, left: int, right: int) -> None:
        """a[left] ~ a[right]를 힙으로 만들기"""
        temp = a[left]      # 루트

        parent = left
        while parent < (right + 1) // 2:
            cl = parent * 2 + 1     # 왼쪽 자식
            cr = cl + 1             # 오른쪽 자식
            child = cr if cr <= right and a[cr] > a[cl] else cl  # 큰 값을 선택합니다.
            if temp >= a[child]:
                break
            a[parent] = a[child]
            parent = child
        a[parent] = temp

    n = len(a)

    for i in range((n - 1) // 2, -1, -1):   # a[i] ~ a[n-1]을 힙으로 만들기
        down_heap(a, i, n - 1)

    for i in range(n - 1, 0, -1):
        a[0], a[i] = a[i], a[0]     # 최댓값인 a[0]과 마지막 원소 a[i]를 교환
        down_heap(a, 0, i - 1)      # a[0] ~ a[i-1]을 힙으로 만들기

if __name__ == '__main__':
    print('힙 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요. : '))
    x = [None] * num    # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}] : '))

    heap_sort(x)        # 배열 x를 힙 정렬

    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

 

시간 복잡도

 

단순 선택 정렬은 아직 정렬하지 않은 모든 원소 중에서 최댓값을 선택한다. 힙 정렬은 맨 앞 원소를 꺼내는 것만으로 최댓값을 구할 수 있지만 남은 원소를 힙으로 재구성해야 한다.

단순 선택 정렬에서 최갯값인 원소를 선택하는 시간 복잡도는 O(n)이지만, 힙 정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(log n)이다.

 

따라서 단순 선택 정렬의 시간 복잡도는 O(n^2)이지만, 힙 정렬은 원소의 개수만큼 작업을 반복하므로 전체 정렬하는 데 걸리는 시간 복잡도는 O(n log n)으로 크게 줄어든다.