[알고리즘] 정렬 알고리즘 - 힙 정렬

1. 힙(heap)이란?

힙(heap)은 완전 이진 트리로서, 각 노드의 값은 자신의 자식 노드의 값보다 크거나 같다는 조건을 만족한다.

따라서 최댓값은 항상 루트노드에 위치하며, 이렇게 오름차순 정렬을 하는 경우 최대 힙(maximum heap)이라 한다.

※ 만약 내림차순 정렬을 하는 경우에는 최소 힙(minimum heap)이라 한다.

아래 그림과 같은 완전 이진 트리가 힙이다.

위의 그림의 오른쪽에도 있지만, 이러한 힙을 일차원 배열로 구현하여 인덱스를 활용하면, 두 자식 노드의 위치를 찾아가기 쉽다.

60(i=1)의 자식 노드는 40(2*i+1=3)과 20(2*i+2=4)로, 단순한 계산을 통해 자식 노드의 위치를 알 수 있으며, 이를 반대로 적용할 경우, 부모 노드를 찾아갈 수 있다.

 

힙에 새로운 값 90을 삽입하는 경우, 다음과 같은 과정을 거친다.

우선 새로운 노드를 추가하려면 마지막 레벨의 빈자리 중 맨 왼쪽에 추가해야한다. 이 경우 40의 자식 노드이자, 10의 형제 노드에 위치하게 된다. 이후 삽입 노드와 부모 노드 비교를 통해 부모 노드보다 삽입 노드가 클 경우 부모 노드와 자리를 바꿔나가며, 해당 노드의 위치를 찾게 된다. 

 

그렇다면 이번에는 최대값을 삭제하는 방법에 대해 살펴보자. (최대힙의 경우는 최대값, 최소힙의 경우 최소값이다.)

최대값을 삭제하는 방법은, 가장 큰 값이 루트 노드에 있으므로, 루트 노드와 가장 마지막 레벨의 가장 마지막 노드와 자리를 바꾸는 것이다. 이후 가장 마지막으로 간 최대값은 삭제하고, 루트 노드로 올라간 값을 비교를 통해 자리를 바꿔주게 되는데, 이 때 주의할 점은 자식 노드 중 더 큰 값과 자리를 바꿔야 한다는 것이다. 그래야 그 다음 가장 큰 자식 노드가 루트 노드로 올라가게 되기 때문이다.

 

 

2. 힙 정렬

힙 정렬은 이러한 힙 자료구조가 갖는 장점을 이용한 정렬 방식이다.

입력 데이터가 배열로 주어지면 이를 초기 힙으로 변환하고, 최대값을 삭제하고 힙으로 재구성하는 과정을 통해 정렬을 하는 것이다.

 

① 알고리즘

def HeapSort(A[],n):
    for i in range(n): # 초기 힙 생성
        par = (i-1) // 2 # 부모 노드의 위치 찾기
        while (par >= 0 and A[par] < A[i]) : # 부모 노드가 더 작을 때
            A[par], A[i] = A[i], A[par] # 위치 변경
            i = par
            par = (i-1) // 2 # 그 위치 변경한 것에서 다시 부모 노드를 찾아 다시 비교
    
    for i in range(n-1, 0, -1):
        A[0], A[i] = A[i], A[0] # 마지막 노드와 최대값 변경
        cur = 0
        lch = 1
        rch = 2
        while True :
            if (rch < i && A[lch] < A[rch]): # rch가 더 큰 경우
                lch = rch # lch를 rch로 바꿔놓음
            if A[lch] > A[cur] : # 만약 자식노드 중 큰 값이 현재 노드보다 크다면
                A[cur], A[lch] = A[lch], A[cur] # 자리를 바꿈
                cur = lch # 그리고 자식 노드 위치로 current 위치를 바꿔놓고
                lch = cur *2 + 1 # 그 자식 노드의 자식 노드로 lch, rch 변경
                rch = cur *2 + 2
            else :
                lch = i # 자식노드 중 큰 값보다 부모 값이 크다면, lch = i로 해놓자
            if lch < i : # 여전히 i에 반해 lch가 작다면
                continue # while문 반복
            break # 아니면 while문 탈출
    return A

 

힙에 대해 설명하면서 새로운 노드 삽입법과 최대값을 삭제하는 방법에 대해 설명했으므로, 예시는 생략하겠다.

 

② 성능 분석

힙 정렬은 초기 힙 생성과 최대값 삭제 및 힙 재구성이라는 두 개의 이중 루프로 알고리즘이 구성된다.

초기 힙을 생성하는 이중 루프는 바깥쪽은 입력 크기 n만큼 반복, 안쪽 루프는 리프 노드에서 최대 루트 노드까지 진행하면서 힙 조건 만족 여부를 조사하기 때문에 완전 이진 트리의 높이인 logn에 비례한다.

최대값 삭제 및 힙 재구성에 대한 이중르프도 바깥쪽은 입력 크기 n에 비례, 안쪽 루프는 루트 노드에서 최대 리프 노드까지 진행하면서 힙 조건의 만족 여부에 따라 비교, 교환이 이루어져 logn에 비례한다.

따라서 힙 정렬 알고리즘의 시간복잡도는 O(nlogn)이 된다.

 

③ 특징

• 안정적이지 않은 정렬 알고리즘이다.
• 제자리 정렬 알고리즘이다. 힙을 제외하곤 변수는 상수 개만큼 필요로 한다.