Heap_sort(힙 정렬) [java]

Heap_sort

개념

- 최대 힙 트리나 최소 힙 트리를 이용해 정렬을 하는 방법

- 최악의 경우 시간 복잡도 : O(nlogn)

- 추가 배열이 불필요

- 이진 힙 자료구조를 사용

 

1. 정렬해야 할 n개의 요소들을 최대 힙을 만든다.

- 최대 힙 - 완전 이진 트리 : 부모 노드의 가장 큰 값, 자식 노드에 작은 값으로 만든다.

2. 완전 이진 트리에서 루트의 값이 가장 큰 값 혹은 가장 작은 값이므로 배열에 정렬시키고 그 값은 다음 계산부터는 제외시킨다.

 

** Heap 

- complete binary tree

- heap property

위 두 가지를 모두 만족해야 heap이라 할수 있다.

 

complete binary tree : 마지막 레벨을 제외하면 완전히 꽉 차있고, 마지막 레벨에는 오른쪽부터 연속된 몇 개의 노드가 비어있을 수 있다.

 

heap property : max heap property(부모 >= 자식) , min heap property(부모 <= 자식) 

heap의 예시

** 같은 데이터일지라도 heap의 형태는 다를 수 있다!!

 

배열로 표현

* 힙은 일차원 배열로 표현이 가능하다. A[1...n]

- 루트 노드 A[1]

- A[i]의 부모 = A[i/2]

- A[i]의 왼쪽 자식 = A[2i]

- A[i]의 오른쪽 자식 = A[2i+1]

 

힙의 1차원 배열 모습

힙 만들기

- 기본 연산 : MAX-HEAPIFY

이 경우를 위해서 트리 전체의 모양은 complete binary tree모양이고 루트만이 heap property를 만족하지 않는 경우이다. -> 왼쪽 서브 트리와 오른쪽 서브트리는 각각의 부모 노드들이 자식노드보다 크지만 루트의 경우는 자식보다 작은 경우!!

- MAX-HEAPIFY를 하고 난 뒤 노드들의 모습이다.

 

MAX-HEAPIFY의 수도코드

1. 자식이 없는 경우에는 바로 return해준다.

2. 자식중 큰 값을 k에다가 넣고 현재 루트와 k를 비교하여 루트가 더 크면 그대로 return, 작으면 두 값을 교환한다.

3. k를 루트로 MAX-HEAPIFY를 호출한다.

 

위의 수도 코드의 시간 복잡도는 트리의 계층 수 이다.

이진 트리이므로 반반씩 나눠진다 따라서 개수가 n개이면 시간복잡도는 O(logn)이다.

 

BULID-MAX-HEAP 수도코드

1. 부모 노드들의 값들만 가지고 MAX-HEAPIFY를 하면되므로 마지막 값의 나누기 2를 한 값부터 1씩 줄이면 값으로 MAX-HEAPIFY를 호출한다.

 

** 시간복잡도 : 여기서 MAX-HEAPIFY의 시간복잡도는 아까 logn이라고 했다. 따라서 개수가 n개이면 nlogn이 된다.

하지만 중요한 것이 있다. logn인 경우는 가장 마지막 경우 즉 root일때만 성립한다. root가 아닐 때는 비교할 개수가 n개가 아니므로 logn이 아니게 된다. 따라서 위의 수도코드를 더 정확하게 계산하면 nlogn보다 작게 된다.

 

heap_sort정리

- 생각해보니 heap_sort를 위해서 준비한 것이 엄청 많았던것 같다. 이제 heap_sort의 최종 정리를 해보겠다

1. BUILD-MAX-HEAP을 이용해 임의로 주어진 배열을 heap으로 만들어 준다.

2. 이렇게 되면 가장 앞에 있는 값이 최댓값이 된다.

3. 최댓값과 마지막 값을 바꿔주고 마지막 값을 갖고 MAX-HEAPIFY를 호출한다.

4. 이때 배열상에서 마지막 값은 더 이상 생각하지 않는다.

 

HEAPSORT의 수도코드

위의 수도 코드의 시간 복잡도는 for문에서 n-1번 반복되고 max-heapfiy의 logn이어서 결국 nlogn이 된다.

 

코드

package sort;

import java.util.Arrays;

public class heap_sort {
    public static void main(String[] args) {
        int[] base = new int[]{4, 2, 7, 9, 10, 1, 3, 5, 13, 11};
        HEAPSORT(base);
        System.out.println(Arrays.toString(base));
    }

    public static void MAX_HEAPIFY(int[] base, int i, int len){
        int j;
        int tmp = base[i-1];
        while(i<=len/2){ // 자식 존재 여부
            j = i*2;
            if((j<len) && (base[j-1] <base[j])){
                j++;
            }
            if(tmp >= base[j-1]){
                break;
            }
            base[i-1] = base[j-1];
            i=j;
        }
        base[i-1] = tmp;
    }

    public static int[] HEAPSORT(int[] base){
        int len = base.length;
        for(int i = len/2;i>0;i--){
            MAX_HEAPIFY(base,i,len);
        }
        do{
            int tmp = base[0];
            base[0] = base[len-1];
            base[len-1] = tmp;
            len = len-1;
            MAX_HEAPIFY(base,1,len);
        }while(len > 1);

        return base;
    }
}

 

** 위의 그림들은 "영리한 프로그래밍을 위한 알고리즘" 강좌에서 가져왔습니다.