[알고리즘] 힙 정렬

아래 글은 'Do it! 자료구조와 함께 배우는 알고리즘 입문(파이썬 편)'을 보고 정리한 것이다.

힙(Heap)

힙이란, 아래의 조건을 만족하는 완전 이진 트리이다. 힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다. 따라서 힙은 형제의 대소 관계가 정해져있지 않으므로 부분 순서 트리(partial ordered tree)라고도 한다.

 

부모의 값이 자식의 값보다 항상 크다/작다.

인덱스 i에 대해 부모와 자식 인덱스 사이에는 다음과 같은 관계가 성립한다.

• 부모: a[(i-1)//2]
• 자신: a[i]
• 왼쪽 자식: a[i*2 + 1]
• 오른쪽 자식: a[i*2+2]

힙 정렬(Heap Sort)

힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다.

 

힙에서 최댓값은 root에 위치한다.

위와 같은 특징을 이용하여 정렬하는 알고리즘이다. 구체적으로 다음과 같은 작업을 반복한다.

1. 힙에서 최댓값인 root를 꺼낸다.
2. root 이외의 부분을 힙으로 만든다.

1번에서 꺼낸 값을 나열하면 정렬이 끝난 배열이 완성된다. 즉, 힙 정렬은 선택 정렬을 응용한 알고리즘이다. 또한 힙 정렬에서 최댓값인 root를 꺼낸 뒤 다시 남은 원소 중에서 최댓값을 구해야 한다. 위 과정을 조금 더 구체적으로 나열하면 다음과 같다. 우선 주어진 배열을 힙으로 만들어야 한다.

 

1. 가장 아랫단계의 서브트리부터 상향식(bottum-up)으로 전체 배열(트리)을 힙으로 만든다.
2. 힙이자 배열 a의 root인 a[0]는 최댓값이므로 힙의 마지막 원소와 교환한다.
3. 최댓값을 꺼낸 뒤, 0~end-1을 다시 힙으로 구성한다.
4. 2~3번 과정을 반복하며 최댓값을 배열의 마지막부터 채워나간다.

코드

def heap_sort(a):
    def down_heap(a, left, right):
        parent = left
        temp = a[parent]

        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
        return

    n = len(a)

    ## heapify
    for i in range((n-1)//2, -1, -1):
        down_heap(a, i, n-1)

    ## sort
    for i in range(n-1, 0, -1):
        a[0], a[i] = a[i], a[0]
        down_heap(a, 0, i-1)

down_heap(a, left, right) 함수

배열 a에서 a[left]~a[right] 원소를 힙으로 만든다. a[left] 이외에는 모두 힙 상태라고 가정하고 a[left]를 아랫단계의 알맞은 위치로 옮겨 힙 상태로 만든다.

heap_sort(a) 함수

원소 수가 n인 배열 a를 힙 정렬하는 함수이다. 다음과 같이 2단계로 구성된다.

1. down_heap() 함수를 호출하여 배열 a를 힙으로 만든다.
2. 최댓값인 root a[0]를 꺼내 배열의 마지막 원소와 교환하고, 배열의 남은 부분을 다시 힙으로 만드는 과정을 반복하여 정렬을 수행한다.

힙 정렬의 시간 복잡도

힙 정렬은 맨 앞 원소를 꺼내는 것만으로 최댓값을 구할 수 있지만, 남은 원소를 힙으로 재구성해야 한다. 단순 선택 정렬에서 최댓값인 원소를 선택하는 시간 복잡도는 O(n)이지만, 힙 정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(log n)이다. 루트를 알맞은 위치까지 내리는 작업은 스캔할 때마다 선택 범위가 절반으로 줄어드는 이진 검색(Bianary Search)과 비슷하다. 따라서 단순 선택 정렬의 시간 복잡도는 O(n^2)이지만, 힙 정렬은 원소의 개수만큼 작업을 반복하므로 전체 정렬하는 데 걸리는 시간 복잡도는 O(n log n)이다.

heapq 모듈

import heapq
def heap_sort(a):
    heap = []
    for i in a:
        heapq.heappush(heap, i)
    for i in range(len(a)):
        a[i] = heapq.heappop(heap)