힙 정렬 (Heap sort) - 1

힙 정렬은 힙, 바이너리 힙, 이진 힙이라고 부르는 자료구조를 이용하는 정렬 알고리즘입니다.

힙 정렬의 특징은 다음과 같습니다.
1.최악의 경우에도 시간 복잡도가 nlogn이 되는 빠른 정렬이다.
2.힙 정렬은 알고리즘을 구현하는데 추가적인 배열이 필요하지 않다.
3.이진 힙(바이너리 힙) 자료구조를 사용한다.

먼저 힙 정렬을 구현하기 전에, 힙 이라는 자료구조에 대해 알아보겠습니다.

힙(Heap) 이란?

힙(Heap)은

1. complete binary tree(완전 이진 트리) 이면서
2. heap property를 만족해야 합니다.

위의 그림에서는 **full binary tree(포화 이진 트리)**와 **complete binary tree(완전 이진 트리)**에 대해 설명하고 있습니다.

binary tree(이진 트리)란 한 노드가 최대 2개의 자식 노드를 가지는 트리 입니다. 따라서, 위의 2개 트리는 모두 이진 트리입니다. 이진 트리는 이진 탐색 트리(BST)와 이진 힙(Binary Heap)의 구현에 흔히 사용됩니다.

full binary tree(포화 이진 트리)란 이진 트리중에 모든 레벨의 노드 들이 꽉 차있는 형태를 말합니다.

complete binary tee(완전 이진 트리)는 마지막 레벨을 제외하면 완전히 꽉 차있고, 마지막 레벨에는 가장 오른쪽 부터 연속된 몇개의 노드가 비어있을 수 있는 트리를 말합니다. 따라서 포화 이진 트리는 완전 이진 트리이기도 합니다.

위의 2번째 조건에서 heap property를 만족해야 한다고 했습니다. 이 heap property는 2개의 조건으로 나누어집니다.

1. max heap property - 부모 노드는 자식 노드보다 데이터가 크거나 같다.
2. min heap property - 부모 노드는 자식 노드보다 데이터가 크거나 작다.

max와 min 모두 대칭적 관계이므로 모든 알고리즘에 적용되나 상황에 따라서 간단하게 사용할 수 있는 것을 씁니다. 여기서는 max-heap property를 다루겠습니다.

(a)의 3개 트리는 모두 heap 입니다. (완전 이진 트리이면서 heap property를 만족합니다.)
(b)의 3개 트리는 heap이 아닙니다. (완전 이진 트리이지만, (max)heap property를 만족하지 않습니다.)
(c)의 2개 트리도 heap이 아닙니다. (완전 이진 트리를 만족하지 않습니다.)

위의 (a), (b), (c)는 모두 다 heap입니다.
(a), (b), (c)는 동일한 데이터를 갖고 있는 서로 다른 heap입니다. 즉, 여러가지 모양의 heap이 존재할 수 있는 것입니다.

Heap은 1차원 배열을 사용해 표현할 수 있습니다. 같은 레벨에서 왼쪽부터 배열로 저장하면 1차원 배열이 됩니다. 일반적인 트리에서는 부모 자식간의 관계를 식을 통해 표현할 수 없지만 Heap은 complete binary tree이므로 배열의 인덱스만으로 부모와 자식의 관계를 표현할 수 있습니다. 루트 노드가 배열의 1번 인덱스부터 시작한다면 다음과 같은 표현식을 사용할 수 있습니다.

• 루트 노드 : A[1]
• A[i]의 부모 노드 : A[i/2]
• A[i]의 왼쪽 자식 노드 : A[2i]
• A[i]의 오른쪽 자식 노드 : A[2i+1]

따라서 Heap은 1차원 배열을 통해 표현이 가능하기 때문에 불필요하게 트리 자료구조를 따로 만들어 사용해 구현할 필요가 없습니다.

Max-heapify 란?

지금부터는 어떤 1차원 배열의 데이터가 있을 때 이 1차원 배열을 Heap으로 변환하는 과정에 대해 알아보겠습니다. (이번 포스팅에서는 max heap만을 다루기로 했으므로 max heap을 만드는 방법에 대해 알아보겠습니다.)
일반 1차원 배열은 max-heapify라는 연산 과정을 통해 max heap으로 만들수 있습니다.

max-heapify 연산을 하기 위한 전제조건을 위의 그림에서 보여주고 있습니다.

1. 트리의 전체 모양은 complete binary tree이다.
2. 왼쪽 서브 트리(subtree)는 그 자체로 heap이다.
3. 오른쪽 서브 트리(subtree)는 그 자체로 heap이다.

여기서 유일하게 루트 노드만이 heap property를 만족하지 않을때, max-heapify 연산을 통해 heap property를 만족하게 만들 수 있습니다.

위의 그림에서 루트 노드는 자신의 자식 노드중에 더 큰값과 자리를 교체 합니다. 그 후 교체된 노드에서 다시 max-heapify 연산을 통해 max-heap property를 만족할 때까지 반복합니다.

결국 max-heapify는 동일한 과정을 반복하고 있기 때문에 **recursion(재귀)**로 구현이 가능합니다.

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;
    exchange A[i] and A[k];
    MAX-HEAPIFY(A, k);
}

첫번째 조건은 base case로서, 자식 노드가 없다면 가장 아래의 레벨에 위치한 리프노드이기 때문에 종료합니다. 만약 자식 노드가 있다면 큰 자식 노드의 인덱스를 k로 지정합니다. 그 후 부모 노드와 값을 비교해 부모 노드가 크다면 max-heapify 과정을 종료하고, 자식 노드의 값이 크다면 부모 노드와 값을 교환한 후 다시 max-heapify를 재귀 호출 합니다.

MAX-HEAPIFY(A, i){
    while A[i] has a child do
        k<- index of the biggest child of i;
        if A[i]>= A[k];
            return;
        exchange A[i] and A[k];
        i=k;
    end
}

같은 함수를 iterate하게 구현한 코드입니다. 주요 함수의 동작 원리는 같습니다.

max-heapify의 시간 복잡도는 루트 노드로부터 마지막 레벨까지 비교, 교환 연산을 하므로 트리의 높이보다 많은 시간이 필요하지 않습니다. 따라서 시간 복잡도는 높이에 의해서 결정되며, O(h)입니다.
일반적인 이진트리가 아닌 complete binary tree이므로 노드의 개수를 n이라 하면, **시간 복잡도는 O(logn)**이 됩니다.

출처 : 2015 봄학기 알고리즘 - 부경대 권오흠 교수님