[Week1] 힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

정의

완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로 한 정렬 방식

불안정 정렬에 속한다. 

 

※ 완전 이진트리
   마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 
   마지막 레벨의 모든 노드는 가능한 가장 왼쪽에 있다.

 

퀵 정렬과 합병 정렬의 성능이 좋기 때문에 힙 정렬의 사용 빈도가 높지는 않다.

힙 자료구조의 활용 시에 알아두면 좋음

 

힙 정렬이 유용할 때

• 가장 크거나 가장 작은 값을 구할 때
  : 최소 힙 or 최대 힙의 루트 값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능
• 최대 k만큼 떨어진 요소들을 정리할 때
  : 삽입 정렬보다 더욱 개선된 결과를 얻을 수 있다. 

Process

1. 최대 힙을 구성

2. 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임

3. 힙의 사이즈가 1보다 크면 위 과정 반복

루트를 마지막 노드로 대체 (11 → 4)

다시 최대 힙 구성

 

자바 코드

public void heapSort(int[] array) {
    // array = [4, 2, 7, 1, 6, 5, 3]
    int n = array.length;
    
    // max heap 초기화
    for (int i = n/2-1; i>=0; i--){
        heapify(array, n, i); // 1
    }
    // (array, 7, 2) -> 2, 5, 6 -> [4, 2, 7, 1, 6, 5, 3]
    // (array, 7, 1) -> 1, 3, 4 -> [4, 6, 7, 1, 2, 5, 3]
    // (array, 7, 0) -> 0, 1, 2 -> [7, 6, 4, 1, 2, 5, 3]
    // (array, 7, 2) -> 2, 5, 6 -> [7, 6, 5, 1, 2, 4, 3]
    
    // extract 연산
    for (int i = n-1; i>0; i--) {
        swap(array, 0, i); 
        heapify(array, i, 0); // 2
    }
}

 

 

1. 일반 배열을 max 힙으로 초기화하는 역할
   부모 노드부터 자식 노드들을 비교
2. 요소가 하나 제거된 이후에 다시 최대 힙을 구성하는 역할
   루트를 기준으로 진행

public void heapify(int array[], int n, int i) {
    int p = i;
    int l = i*2 + 1;
    int r = i*2 + 2;
    
    //왼쪽 자식노드
    if (l < n && array[p] < array[l]) {
        p = l;
    }
    //오른쪽 자식노드
    if (r < n && array[p] < array[r]) {
        p = r;
    }
    
    //부모노드 < 자식노드
    if(i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}

 

최대 힙을 구성할 때까지 부모 노드와 자식 노드를 swap하며 재귀 진행

 

 

시간복잡도

평균	최선	최악
Θ(nlogn)	Ω(nlogn)	O(nlogn)