힙정렬(Heap Sort)

힙정렬(Heap Sort)는 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 

따라서 힙(Heap) 자료구조를 잘 이해하고 있어야 하기 때문에 반드시 관련 POST를 읽고 이 글을 읽어야 한다.

 

알고리즘은 힙에 자료를 추가하고 최대값 또는 최소값을 하나씩 삭제하는 것과 동일한데

 

Note - 힙정렬 알고리즘

1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.
2. 최대힙(내림차순정렬이 필요한경우) 인경우 루트노드가 자식노드보다 항상 크도록하고 최소힙(오름차순 정렬이 필요한경우)인경우 로트노드가 자식노드보다 항상 작도록 구성한다. 힙정렬에서는 이 과정을 heapify 라고 한다.
3. 이진힙을 구성되면 루트노드는 항상 최대값 또는 최소값으로 되어 있기 때문에 루트노드를 원소의 개수만큼 삭제과정을 거치면서 정렬된 데이터를 얻을 수 있다. (단, 루트노드가 삭제시 이진힙이 깨지기 때문에 삭제후  이진힙이 되도록 해야한다.)

▲ [출처] https://slideplayer.com/slide/4972695/

 

이진힙은 배열 또는 노드로 구현 가능한데 보통 배열이 이해하기 쉽고 더 빠른 엑세스를 제공하기 때문에 배열로 구현하는것이 좋다.

이진힙은 완전이진트리(complete binary tree) 때문에 배열로 표현하면 위 그림처럼 되고 좌측노드, 우측노드, 부모노드를 탐색하는데 필요한 공식도 매우 심플하다. 

 

그림과 공식을 확인했으니 구현에 들어가겠다.

여기서는 최대힙을 통해 오름차순 heap 정렬을 할 것이고 그림과 약간 다름점은 root 가 배열 index=1  에 있는것이 아니고 0에 있는것으로 하겠다. 그럼 공식이 약간 달라지는데  left(i) = 2*i + 1 , right(i) = 2*i + 2 , parent(i) = (i-1)/2 로 변경된다. 

Note - 힙소트 코드 구현 단계

1. 주어진 데이터로 힙을 만든다(heapify)
2. 힙에서 최대값(루트)을 가장 마지막 값과 바꾼다(swap).
3. 힙의 크기가 1 줄어든 것으로 간주한다. 즉, 가장 마지막 값은 힙의 일부가 아닌 것으로 간주한다.
4. 맨마지막 값이 배열 맨 처음으로 swap 되었으니 최대힙이 깨질수 있으니 자식노드와 비교하여 루트노드가 최대값이 올 수 있도록 다시 구성해준다. (shiftDonw)
5. 2-4번을 반복한다.

제일 먼저 heapify 를 해야하는데 추가적인 배열을 메모리에 할당하지 않고 정렬되지 않은 배열을 최대힙으로 만들기위해서 어떻게 해야할까 ?

 

Note - 힙소트 heapify 알고리즘

 

1. 주어진 배열 ( array = [4, 10, 3, 5, 1] ) 을 우선 완전이진트리(complete binary tree)로 표현한다.
2. 완전이진트리에서는 특정 노드의 왼쪽자식노드(left child node) = 2*index + 1, 오른쪽자식노드(right child node) = 2*I +@ 공식을 사용한다. (i는  left, right 자식을 찾기위한 노드의 배열 인덱스이다.)
위 그림을 예로 들면 array[1] = 10 노드의 왼쪽자식노드는 공식을 통해  2*1 + 1 = 3 이 되서 5를 가진 노드의 인덱스를 얻을 수있고 오른쪽 자식노드는 2*1 + 2 = 4 가 되어 1을 가진 노드의 인덱스를 얻을 수 있다

3. heapify 시작할 위치는 뒤에서부터 leaf 노드(자식노드가 없는)가 아닌 노드부터 시작된다.  노드 5, 1, 3 들을 자식노드가 없는 leaf 노드들인데 작은 서브힙으로 간주한다면 이미 최대힙 속성을 만족하기 때문에 체크할 필요가 없는것이다. 
그럼 배열 뒤부터 1 -> 5 -> 3 으로 살펴보다가 젤 처음으로 자식노드를 가진 노드는 10 이다. 
최소 하나의 자식노드를 가진 노드를 인덱스를 찾기위한 공식은 (배열사이즈/2)  - 1 이고 대입하면 여기서 1이 되고 정확히 10을 가진 노드의 인덱스를 가리킨다. 

4. index=1인 10번 노드를 부모노드와 비교하여 크다면 서로 swap 한다. 
index=1인 10번 노드는 부모노드 4보다 값이 크므로 서로 swap 되고 4번은 하위 왼쪽자식노드 5 보다 작기 때문에 4와 5도 서로 swap 해주어야 한다. 

5. 처음 시작한 index를 하나씩 감소시키면서 4번을 반복하면 최대힙이 구성된다. 

 

 

 

 
public class Main {
 
    public static void main(String[] args)  {
 
        int array[] = {14, 33, 27, 10, 35, 19, 42, 44};
        heapSort(array);
 
        for (int i = 0 ;i < array.length ; i++){
            System.out.print(array[i] + " ");
        }
    }
 
    public static void heapSort(int[] a){
        int count = a.length;
 
        // 1. 주어진 데이터로 힙을 만든다(heapify)
        heapify(a, count);
 
        int end = count - 1;
        while(end > 0){
            // 2. 힙에서 최소값(루트)을 가장 마지막 값과 바꾼다. -> 배열의 맨 뒤로 보낸다.
            int tmp = a[end];
            a[end] = a[0];
            a[0] = tmp;
 
            // 3. 힙의 크기가 1 줄어든 것으로 간주한다. 즉, 가장 마지막 값은 힙의 일부가 아닌 것으로 간주한다.
            end--;
 
            // 4. 맨마지막 값이 배열 맨 처음으로 swap 되었으니 최대힙이 깨질수 있으니
            // 자식노드와 비교하여 루트노드가 최대값이 올 수 있도록 다시 구성해준다
            siftDown(a, 0, end );
 
 
        }
    }
 
    public static void heapify(int[] a, int count){
// heapify 시작할 위치는 뒤에서부터 leaf 노드(자식노드가 없는)가 아닌 노드부터 시작된다
        int start = (count/2)/ - 1;
 
        while(start >= 0){
            siftDown(a, start, count - 1);
            start--;
        }
    }
 
    public static void siftDown(int[] a, int start, int end){
        int root = start;
 
        // 루트노드의 자식노드가 있을 때 까지 루트노드가 최대값이 오도록 비교한다.
        while((root * 2 + 1) <= end){
            int child = root * 2 + 1; //root*2+1 은 왼쪽자식노드 배열 index 이다.
            int right = child + 1; // 오른쪽 자식 노드를 배열 index 이다.
 
 
 
            // 노드의 키와 부모노드의 키를 비교하여 스왑(swap)이 필요한경우 swap 한다.
            // 왼쪽, 오른쪽 비교하여 둘 중에 오른쪽서브트리로 결정해야하는 경우임.
            if (right <= end &&  a[child] < a[right])
                child = right;
 
            // 루트와 자식노드의 값을 비교하여 루트가 작다면 swap 한다.
            if(a[root] < a[child]){
                int tmp = a[root];
                a[root] = a[child];
                a[child] = tmp;
                root = child;
            }
            else {
                return;
            }
        }
    }
 
 
}
 

레퍼런스

• 제6-3강 힙 정렬(heap sort)
• https://javabypatel.blogspot.com/2015/11/heap-sort-algorithm.html