Heap sort

1. Problem

 - 힙을 이용해 배열의 값을 오름차순으로 정렬해보자.

 // 완전 이진 트리(complete binary tree): 자식 노드가 왼쪽부터 채워지는 이진 트리. 같은 레벨의 중간 부분이 비어있지 않다.

// 힙: 최댓값/최솟값을 빠르게 찾기 위해 완전 이진 트리를 기반으로 만들어진 트리

// 최대 힙: 부모 노드가 자식 노드보다 큰 값을 갖는 힙

// 힙 생성(heapify) 알고리즘: 특정 노드를 최대 힙에 넣는 알고리즘. 특정 노드의 두 자식 중 더 큰 자식과 자기 자신의 위치를 바꾸면서 자리를 찾아 간다.

 

2. Input

1) int[] heap

 

3. Output

1) heap을 오름차순으로 정렬한 결과

 

4. Example

// 위쪽 그림에서의 최대 힙: 6 5 2 4 1
// 6의 자식 중 6보다 큰 수는 없다.
// 6과 맨 뒤 자식의 자리를 바꾼다. -> 1 5 2 4 (6)
// 1의 자식 중 5가 가장 크므로 1과 5의 자리를 바꾼다. -> 5 1 2 4 (6)
// 5와 뒤쪽 자식의 자리를 바꾼다. -> 4 1 2 (5 6)
// 4의 자식 중 4보다 큰 수는 없다.
// 4와 뒤쪽 자식의 자리를 바꾼다. -> 2 1 (4 5 6)
// 2의 자식 중 2보다 큰 수는 없다.
// 2와 뒤쪽 자식의 자리를 바꾼다. -> (1 2 4 5 6)

 

5. Code

int[] heap = {6, 3, 5, 9, 1, 10, 7, 2, 4, 8}; // 10개의 요소
// 0번이 root이고, 1, 2번이 root의 자식, ...
//       6
//    3     5
//  9   1 10  7
// 2 4 8          heap는 이런 식의 완전 이진트리를 표현하고 있다.

// 최대 힙 생성
for(int i=1 ; i<heap.length ; i++) {
    int c = i;                    // 현재 노드의 위치
    while(c!=0) {
        int root = (c-1)/2;       // c의 부모 노드의 위치
        if(heap[root]<heap[c]) {  // c가 부모보다 큰 수라면
            int tmp = heap[root]; // 자리를 바꾼다.
            heap[root] = heap[c];
            heap[c] = tmp;
        }
    c = root;                 // 부모 노드의 값에 대해
    }                             // 최대 힙이 될 수 있게 정렬을 다시 수행한다.
}

// 최대 힙 정렬 확인
for(int i : heap)
    System.out.print(i+","); // 10,8,9,4,6,5,7,2,3,1,
//      10
//    8     9
//  4   6  5  7
// 2 3 1          최대 힙을 만족하고 있는 것을 확인할 수 있다.

// 힙을 오름차순으로 정렬
for(int i=heap.length-1 ; i>=0 ; i--) { // 최댓값을 찾는 범위를 1개씩 줄여나간다.
    int tmp = heap[0];   // 맨 앞과 맨 뒤의 값을 바꾼다.
    heap[0] = heap[i];   // 맨 앞의 값을 가장 크므로
    heap[i] = tmp;       // 뒤로 보내는 것이다.
    int root = 0, c = 1; // 부모, 자식 노드의 위치
    while(c<i) { // i번째까지는 정렬이 됐다고 가정하고, 나머지 노드 중 가장 큰 값을 찾는다.
        c = 2*root + 1; // 부모의 왼쪽 자식 노드의 위치
        if(c<i-1 && heap[c]<heap[c+1]) // 왼쪽, 오른쪽 자식 중 더 큰 것 찾기
            c++;
        if(c<i && heap[root]<heap[c]) {  // c가 부모보다 큰 수라면
            tmp = heap[root];     // 자리를 바꾼다.
            heap[root] = heap[c];
            heap[c] = tmp;
        }
        root= c; // 범위 내에 가장 큰 수가 루트로 올 때까지 반복한다.
    }
}

// 힙 오름차순 정렬 확인
for(int i : heap)
    System.out.print(i+","); // 1,2,3,4,5,6,7,8,9,10,

- 1개의 요소에 대해 힙 생성 알고리즘을 수행하는 횟수는 lgn번이다.

- n개의 요소라면 비교 연산의 총 횟수는 n*lgn번이다.

- 그러므로 시간 복잡도는 O(n*lgn)를 따른다.

- 힙 정렬은 병합 정렬과 다르게 추가 배열이 필요하지 않다.

- 속도는 퀵 정렬이 평균적으로 빠르기 때문에 일반적으로는 퀵 정렬을 더 많이 사용한다.