[Algorithm] 힙 정렬 (Heap Sort)

완전이진트리(complete binary tree)

• 완전 : 루트(root) 노드부터 시작해 왼쪽, 오른쪽 순으로 자식 노드부터 추가하는 모양
  
• 이진 : 부모가 가질수 있는 자식의 개수는 최대 2개
  
• 트리 : 요소의 상하 관계를 부모(parent)와 자식(child), 자식 간의 관계를 형제(sibling)
  
• 루프 : 트리의 첫 노드
  
• 리프 : 트리의 마지막 노드

 

자료구조 ‘힙(heap)’

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조
• 최대 힙 : '부모의 값이 자식의 값보다 항상 큰' 조건을 만족하는 완전이진트리
• 최소 힙 : '부모의 값이 자식의 값보다 항상 작은' 조건을 만족하는 완전이진트리

자식과 부모 관계식

• 부모 : a[(i - 1) / 2]
• 왼쪽 자식 : a[(i * 2) + 1]
• 오른쪽 자식 : a[(i * 2) + 2]

힙 정렬 (Heap Sort)

• 가장 큰 값이 루트에 위치하는 특징을 이용하여 정렬하는 알고리즘이다.
  • 가장 큰 값인 루트를 꺼내는 작업을 반복하고, 그 값을 늘어놓으면 배열 정렬 완료(즉, 선택 정렬을 응용한 알고리즘)
• 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식
  • 완전 이진 트리란? 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리
• 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
  • 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

 

프로세스

1. 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 구성한다
   • 내림차순을 기준으로 정렬
2. 현재 힙 루트는 가장 큰 값이 존재한다. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나를 줄인다.
   
   • 사이즈를 줄이면서 바꿨던 기존의 루트 값은 힙에서 꺼내 배열의 뒤부터 저장한다.
3. 자기보다 큰 값을 가지는 자식 요소와 자리를 교환하며 내려가는 작업을 반복, 이때 자식의 값이 자기보다 작거나 리프(leaf)에 다다르면 종료한다.
4. 삭제되는 요소들(최대값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.

이 정렬을 위해서는 초기 상태의 배열을 최대 힙 상태로 만들어야 한다.

 

단계 정리

1. 최대 힙을 구성
2. 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임
3. 새로운 루트를 자기보다 큰 값을 가지는 자식 요소와 자리를 교환하며 내려가는 작업을 반복, 이때 자식의 값이 자기보다 작거나 리프(leaf)에 다다르면 종료
4. 힙의 사이즈가 1보다 크면 2번 과정부터 반복

(1)

(2)

(3)

(4)

초기 상태의 최대 힙 만들기

1. 가장 아랫부분 오른쪽 부분트리부터 시작해 왼쪽으로 진행하면서 힙으로 만들어줌
2. 가장 아래부분 단계가 끝나면 하나 위쪽으로 부분트리 범위를 확장
3. 다시 왼쪽으로 진행하면서 부분트리를 힙으로 만들어줌

(1)

(2)

(3)

(4)

(5)

 

아래 그림과 같이 힙으로 만드는 과정은 부모 노드와 자식 노드중에서 큰 값을 교환하므로 요소의 개수가 n이라면 n/2개만 보면 된다.

 

ex)

function heapSort(arr) {
    for (let i = arr.length - 1; i >= 0; --i) {
        // 최대 힙으로 다시 초기화
        arr = heapify(arr, i);
        
        // 루트(가장 큰)값과 리프(마지막 요소) 교환
        if (arr[0] > arr[i) arr = swap(arr, i, 0);
    }
    return arr;
}

// arr[leftIdx] ~ arr[rightIdx]의 요소를 힙으로 만드는 함수
function heapify(arr, lastIdx) {
    let idx = parseInt((lastIdx - 1) / 2);
    
    while (idx >= 0) {
        const leftIdx = idx * 2 + 1;   // 왼쪽 자식
        const rightIdx = idx * 2 + 2;  // 오른쪽 자식
       	const child = (arr[leftIdx] > arr[rightIdx]) ? leftIdx : rightIdx; // 자식중 큰 값 설정
        
        // 부모보다 자식이 클 경우, 교환
        if (arr[child] > arr[idx]) arr = swap(arr, child, idx);
        else break;
        
        // 초기 배열 최대힙 과정 : 트리 밑 다시 최대힙 작업 반복
        // 힙정렬 과정: 자식의 값이 자기(루프값) 보다 작거나 리프(leaf)에 다다를때까지 반복
        --idx;  // 부모 노드 한정하여 반복
    }
    
    return arr;
}

function swap(arr, a, b) {
    const temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
    
    return arr;
}

heapify 함수 안에서 idx의 값을 (lastIdx - 1) / 2 해주는 이유?

• 부모 노드의 인덱스를 기준으로 왼쪽 자식노드 (idx * 2 + 1), 오른쪽 자식 노드(idx * 2 + 2)이기 때문

 

heap의 삽입

function insert(arr, data) {
    arr.push(data);
    let i = arr.length - 1;
    
    while (i > 0) {
        const parent = Math.floor((i - 1) / 2);
        if (arr[parent] > arr[i]) break;
        
        swap(arr, i, parent);
        i = parent;
    }
    return arr;
}

• 삽입한 값을 heap의 가장 마지막 단에 추가한다.
• 마지막 노드와 부모의 값을 비교해서 추가한 노드 값이 부모 노드의 값보다 크다면 위치를 바꿔준다.
• 추가한 노드 값이 부모 노드의 값보다 작을 때까지 반복한다.

 

heap의 삭제

function delete(arr) {
    swap(arr, 0, arr.length - 1);
    const max = arr.pop();
    
    heapify(arr);
    
    return max;
}

• heap의 삭제는 heap의 최댓값을 제거하는 동작이다.
• 최댓값이 들어있는 루 노드와 마지막 노드의 자리를 바꿔준 후, 마지막으로 옮겨진 최댓값을 빼낸다.
• 루트 노드에는 마지막 노드의 값이 들어있기 때문에, 다시 heapify를 호출하여 heap 성질을 만족하도록 재정렬해준다.

 

힙 정렬이 유용할 때

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

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

하지만 힙 자료구조가 많이 활용되고 있으며, 이때 함께 따라오는 개념이 힙 정렬.

 

장점

• 시간 복잡도가 O(nlogn)인 빠른 정렬중에 추가적인 메모리가 필요없다.

단점

• 떨어져 있는 데이터 교환이 발생하므로 불안정적 정렬이다.

 

시간 / 공간 복잡도

평균	최선	최악
Θ(nlog₂n)	Ω(nlog₂n)	O(nlog₂n)

• 힙 정렬은 선택 정렬을 응용한 알고리즘이며, 또한 불안정 정렬이다.
• 허나 선택정렬과 다르게 힙 정렬에서는 첫 요소를 꺼내는 것만으로 큰 값이 구해지므로, 첫 요소를 꺼낸 다음 나머지 요소를 다시 힙으로 만들어야 그 다음에 꺼낼 첫 요소도 가장 큰 값을 유지한다.
• 따라서 첫 요소를 선택할때 O(1)이 소요되고, 그 대신 힙 정렬에서 다시 힙으로 만드는 작업은 O(logn)이 소요된다.
• 이진 검색과 비슷하게 스캔할때 마다 스캔의 범위가 반으로 줄어들기 때문이다.
• 요소의 개수가 n개 이므로 시간복잡도는 O(nlogn)이다. 공간 복잡도는 병렬 정렬과 다르게 리스트 안에서 swap하므로 O(n)이다.

 

정렬 알고리즘 시간복잡도 비교

• 단순(구현 간단)하지만 비효율적인 방법
  • 삽입 정렬, 선택 정렬, 버블 정렬
• 복잡하지만 효율적인 방법
  • 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬