힙 정렬(Heap sort)

2017-12-24

algorithms, heap sort, sort

#들어가기

이번 포스팅에는 힙 정렬(heap sort)에 대해 알아보겠습니다.

#힙 정렬(heap sort)

먼저 힙 정렬(heap sort)을 이해하기 위해서 힙(heap) 에 대해 알아보겠습니다.
힙(heap) 은 다음과 같은 두가지 조건을 만족해야 합니다.

complete binary tree
heap property

즉, 완전 이진 트리이면서 힙이 가지고 있는 특성(max or min)을 만족해야 합니다.

포스팅에서는 max heap property를 기준으로 설명하겠습니다.

위의 예시를 보면 (a)는 힙(heap) 이지만 (b), (c)는 힙(heap) 이라고 할 수 없습니다.

(a), max heap property를 만족하면서 완전 이진 트리.
(b), 완전 이진 트리이긴하지만 heap property를 만족하지 않습니다.
(c), max 또는 min property를 만족하지만, 완전 이진트리가 아닙니다.

또 하나 참고로 알아야 할 것이 동일한 데이터를 가지더라도 힙(heap) 은 달라질 수 있습니다. 즉, 힙(heap)은 동일한 데이터에 유일하지 않습니다.

그렇다면 트리로 복잡하게 표현된 힙(heap) 은 어떤 식으로 표현할 수 있을 까요??

각각의 트리에 번호를 루트에서부터 부여해 1차원 배열로 표현이 가능합니다. 이렇게 1치원 배열로 표현된 힙(heap) 을 다루기 위한 기본 연산으로 max-heapify가 필요합니다.

max-heapify를 사용하기 위해서는 트리의 전체 모양이 완전 이진 트리여야 하고 왼쪽 subtree와 오른쪽 subtree가 그 자체로 힙(heap) 이여야합니다. 즉, max-heapify는 루트 노드만이 힙(heap) 을 만족하지 않아 루트 노드를 포함해 힙(heap) 을 만드는 기본 연산입니다.

예시를 한번 보겠습니다. 루트 노드 4를 제외하고 루트를 기준으로 왼쪽 subtree와 오른쪽 subtree는 모두 힙(heap) 을 만족하지만 루트 노드를 포함해서는 힙(heap) 을 만족하지 않는 상황입니다. 이럴 때 max-heapify의 연산으로 루트를 포함한 전체 트리를 힙(heap) 으로 만들수 있습니다.

먼저, max-heapify의 동작 방식부터 보겠습니다. 이번 포스팅에서 max property를 기준으로 하기 때문에 루트 노드 4가 두 자식들 중 더 큰 자식이 나보다 크면 해당 자식과 위치를 교환합니다. 16과 자리를 교체하고 나면 다시 4가 루트인 서브트리를 기준으로 왼쪽 subtree와 오른쪽 subtree는 힙(heap) 을 만족하지만 4를 포함하면 만족하지 않기 때문에 다시 max-heapify 연산을 진행합니다.

max-heapify 연산은 자식이 존재 하지 않거나 두 자식이 나보다 작으면 동작을 멈추게 됩니다.

MAX-HEAPIFY (A, i) {

    if there is no child of A[i]
        return;
    
    k <- index of the biggest child of i;
    
    if A[i] >= A[k]
        return;
        
    exchage A[i] and A[k];
    
    MAX-HEAPIFY(A, k);
}

수도 코드를 보면 자식이 존재하지 않을 때와 또는 두 자식보다 클 경우 종료되는 것을 확인할 수 있습니다.

조금 더 직관적인 예시를 한번 보겠습니다. 루트 노드를 기준으로 왼쪽 subtree가 힙(heap) 을 만족하지 않습니다. 하지만 4를 기준으로 다시 볼때 4의 왼쪽, 오른쪽 subtree 모두 힙(heap) 을 만족하므로 heapify 연산을 사용해 전체를 힙(heap) 으로 만들수 있습니다.

즉, 위의 수도 코드를 사용한다면 MAX-HEAPIFY(A, 2)와 같은 방법으로 전체를 힙(heap)으로 만들 수 있습니다.

자! 그렇다면 이제부터 힙(heap) 과 heapify 연산을 활용해 힙 정렬(heap sort)을 알아보겠습니다.

힙 정렬(heap sort)을 하기 위해서 먼저 정렬해야 할 배열을 완전 이진 트리 형태로 표현합니다. 하지만 이 상태만으로는 힙(heap) property를 만족하진 않습니다. 힙 정렬(heap sort)구현을 위해 첫번째 할 일은 바로 표현된 완전 이진 트리를 힙(heap) 으로 만드는 것 입니다.

표현된 완전 이진 트리를 힙(heap) 으로 만들기 위해서 뒤에서 부터 탐색해 자식이 있는 노드에서부터 앞서 활용했던 max-heapify를 사용합니다. 즉, 16을 기준으로 subtree를 비교하면서 max-heapify를 실행합니다. 16과 subtree는 그 자체로 힙(heap) 이므로 다음 노드인 2로 넘어갑니다.

2를 기준으로 subtree를 비교할때 자식 노드 중 제인 큰 14보다 2는 작은 상황입니다. 따라서 2와 14를 교체합니다. 또 3은 다시 10과 교체하고 1은 16과 교체합니다. 루트 노드까지 올라가면서 max-heapify 연산을하면 힙(heap) 을 완성할 수 있습니다.

즉, 루트 노드가 최대값이 됩니다.

Build-Max-Heap(A) {
    heap-size[A] <- length[A]
    
    for i <- absolute length[A]/2 downto 1  // 배열 A의 길이를 2로 나눈 절대값부터 1까지
        do MAX-HEAPIFY(A, i)
}

수도 코드를 보면 length[A]/2의 절대 값을 취해 자식이 있는 노드 중 가장 밑에 있는 노드부터 시작해 루트 노드까지 MAX-HEAPIFY를 진행합니다.

Build-Max-Heap의 시간 복잡도는 O(n)입니다. MAX-HEAPIFY를 한 번 수행하는데 시간 복잡도는 O(logn)이고 이를 n/2번 실행함으로 시간 복잡도는 O(nlogn)이겠지만 MAX-HEAPIFY가 매번 N만큼 실행 되는 것이 아니므로 보다 정확하게 계산을 진행하면 O(n)이 나옵니다.

그렇다면 정렬되지 않은 배열을 Build-Max-heap을 통해 힙(heap) 형태로 만들어 놓으면 루트 노드는 최대 값이 들어 있는 모양이 됩니다. 이때 루트에 들어있는 최대값을 힙(heap) 의 가장 마지막 값과 바꾸고 힙(heap) 의 사이즈를 1 줄여 줍니다. 그리고 다시 루트에서 부터 heapify를 통해 힙(heap) 으로 만들고 이를 반복합니다.

HeapSort(A) {
    Build-Max-Heap(A); // 배열을 힙으로 만듬 O(n)
    
    for i <- heap_size downto 2 // 정렬 O(n-1)
        exchange A[1] and A[i]  // O(1)
        heap_size <- heap_size -1   // O(1)
        MAX-HEAPIFY(A, 1)   // O(logn)
    
}

결국 모든 힙(heap) 의 요소를 루트 노드에서 빼면서 진행하다 보면 배열은 정렬이 되고 이를 힙 정렬(heap sort)이라고 합니다. 시간 복잡도는 O(nlogn)입니다.

#마치며

이로써 힙 정렬(heap sort)의 정리를 마치겠습니다.

#참조

부경대학교 권오흠 교수님 강의 | 2015년 1학기 - 힙정렬 1
부경대학교 권오흠 교수님 강의 | 2015년 1학기 - 힙정렬 2
부경대학교 권오흠 교수님 강의 | 2015년 1학기 - 힙정렬 3

{DY}

computer sciencealgorithmsconcepts

힙 정렬(Heap sort)

#들어가기

#힙 정렬(heap sort)

#마치며

#참조