힙 정렬 (Heap Sort)

1. 개념 설명

(1) 힙 정렬은 *완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로한 알고리즘이다.

( *완전 이진 트리는 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리를 말한다. )

 

(2) 사실 힙 정렬은 선택 정렬과 거의 같은 알고리즘으로, 단지 가장 큰 원소를 뒤로 보내는 데에 단순히 매번

쭉 돌면서 알아내느냐 힙을 사용하여 알아내느냐가 유일한 차이점이다.

 

 

 

2. 과정

by wiki

by wiki

 

 

 

3. 코드

: 여기서의 코드는 2.과정처럼 배열 한 개씩 넣어서 이진트리를 만드는 것이 아닌 이미

배열의 값들이 순차적으로 트리의 형태로 있다고 가정하고 진행하는 것이다.

 

public class HeapSort {
    static int[] A = { 7, 2, 8, 10, 1 };
    
    public static void main(String[] args) {
        System.out.println("정렬 전: " + Arrays.toString(A));
        heapSort(A.length);
        System.out.println("정렬 후: " + Arrays.toString(A));
    }
    
    public static void heapSort(int len) {
        // 힙 생성
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(len, i);
        }
        System.out.println("완전 이진 트리: " +Arrays.toString(A));
        // 힙 제거
        for (int i = len - 1; i > 0; i--) {
            swap(0, i);
            heapify(i, 0);
        }
    }
    
    // heapify() 함수 역할
    // (1) 일반 배열을 힙으로 구성
    // (2) 요소 하나 제거 이후에 다시 최대 힙으로 구성
    public static void heapify(int len, int i) {
        int p = i;
        int l = i*2 + 1;
        int r = i*2 + 2;
        
        //왼쪽 자식노드
        if (l < len && A[p] < A[l]) {
            p = l;
        }
        //오른쪽 자식노드
        if (r < len && A[p] < A[r]) {
            p = r;
        }
        
        //부모노드 < 자식노드
        if(i != p) {
            swap(p, i);
            heapify(len, p);
        }
    }
    public static void swap(int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}
 

 

 

 

4. 시간 복잡도

(1) 최선, 평균, 최악 모두 O(NlogN)이다.

 

 

 

5. 공간 복잡도

(1) 주어진 배열 안에서 정렬이 일어나므로, 공간 복잡도는 O(n)이다.

 

 

 

6. 장점

(1) 힙 정렬은 추가적인 메모리를 전혀 필요로 하지 않는다.

 

(2) 최악의 경우  O(n²)의 성능을 내는 퀵 정렬과 다르게 항상 O(NlogN) 정렬의 성능을 발휘한다.

 

(3) 퀵 정렬과 같이 피벗을 잡는 전략에 어느 정도의 휴리스틱이 들어가야 최악의 경우를 회피할 수 있으나,

힙 정렬은 휴리스틱 없이 일정한 성능을 보이는 장점이 있다.

( 덕분에 가장 안정적인 성능을 발휘한다. )

 

(4) 힙 정렬은 가장 크거나, 가장 작은 값을 구할 때와 최대 N만큼 떨어진 요소들을 정렬할 때 유용하다.

 

 

 

7. 단점

(1) 퀵 정렬보다 시간복잡도는 좋지만, 일반적인 경우에는 퀵 정렬이 더 빠르게 동작한다.