힙 정렬

힙 정렬

 

힙은 '부모의 값 ≥ 자식의 값'인 관계가 항상 성립하는 완전 이진 트리입니다. 모든 자식의 노드가 2개인 트리 구조라는 것입니다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙입니다. 즉, 이러한 두 값의 대소관계가 일정하면 됩니다.

 

힙은 부모-자식 관계는 일정하지만, 형제 사이의 관계는 일정하지 않습니다. 아래 그림과 같이 7이 6보다 왼쪽에, 5와 4가 3과 2보다 왼쪽에 있지만, 아래 2와1보다 큰 3이 오른쪽에 있는 것처럼 말입니다. 이러한 이유로 부분 순서 트리라고도 합니다.

 

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

 

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

 

힙 정렬 배열이 정렬된 배열인가?

 

힙 정렬은 다음과 같은 과정을 반복합니다. 

1. 힙에서 최대값인 루트를 꺼냅니다.
2. 루트 이외의 부분을 힙으로 만듭니다.

 

즉, 루트를 꺼낸 후 다음과 같은 과정을 통해 힙을 재구성해야합니다. 이렇게 꺼낸 값을 나열하면 정렬이 끝난 배열이 완성됩니다.

 

꺼낸 값을 나열하기

 

① 루트 a[0]에 위치한 최댓값을 꺼내고 배열의 맨 끝 원소인 a[9]와 교환

② a[0] ~ a[8] 힙으로 만들기

③ 다시 a[0]에 위치한 두번째 최댓값을 꺼내고 a[8]과 교환

④ 반복

 

배열을 힙으로 만들기

 

가장 아랫부분의 오른쪽 서브트리의 힙을 만들고, 같은 단계에 있는 왼쪽 서브트리로 진행합니다. 그 단계를 완료하면 한 단계 위로 이동하면서 각각의 서브트리를 힙으로 만듭니다.

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

 

최종 코드

 

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)
     
    """ 1단계 a[i] ~ a[n-1]을 힙으로 만들기 """
    for i in range((n-1) // 2, -1, -1):
        down_heap(a, i, n-1)

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