[Algorithm] 힙 정렬(Heap Sort)

1. 힙 정렬(Heap Sort)이란?

• 힙(heap)을 사용하여 가장 큰 값이 루트에 위치 하는 특징을 이용하는 정렬 알고리즘이다.
• 선택 정렬(selection sort)을 응용한 알고리즘이다. (선택 정렬은 아직 정렬되지 않은 부분의 모든 요소를 대상으로 가장 큰 값을 선택한다.)
• 시간 복잡도는 O(n log n)이다. 

이미지 출처: https://devtut.github.io/algorithm/heap-sort.html#heap-sort-basic-information

1.1 힙(heap)이란?

• 부못값이 자식값보다 항상 크다(부못값 >= 자식값)라는 조건을 만족하는 완전 이진 트리이다. (완전: 부모는 자식을 왼쪽부터 추가하는 모양을 유지 + 이진: 부모가 가질 수 있는 자식의 개수는 최대 2개)
• 트리의 최상단 노드를 루트(root), 트리의 최하단 노드를 리프(leaf), 노드의 상하 관계를 부모(parent)와 자식(child), 자식간의 관계를 형제(sibling)이라고 한다.
• 형제 사이의 대소 관계가 정해져있지 않은 특성이 있어서 부분 순서 트리(partial ordered tree)라고도 한다.

2. 동작 방식

1. 힙에서 가장 큰 값인 루트(root)를 꺼낸다.
2. 마지막 요소를 루트로 옮긴다.
3. 자기보다 큰 값을 갖는 자식 요소와 자리를 바꾸며 아래쪽(왼쪽 -> 오른쪽)으로 내려가는 작업을 반복한다. --> 루트 이외의 요소를 힙으로 만든다.

2.1 배열을 힙으로 만들기

• 초기 상태의 배열이 힙 상태가 아닐 수 있다. 따라서 힙 정렬을 수행하기 전에 먼저 배열을 힙 상태로 만들어야한다.
• bottom-up 방식(아랫부분의 작은 부분 트리부터 시작해 루트까지 올라감) 혹은 top-down방식(루트부터 시작해 리프까지 내려감)으로 전체 배열을 힙으로 만든다.
• 가장 아랫부분의 오른쪽 부분 트리부터 시작해 왼쪽으로 진행하면서 힙으로 만든다. --> 힙 생성 알고리즘(Heapify Algorithm)을 사용한다.

2.2. 힙 생성 알고리즘(Heapify Algorithm)이란?

• 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다.
• 특정한 노드 하나에 대해서 수행한다.

3. 구현하기

1. downHeap 메서드를 사용하며 배열을 힙(heap)으로 만든다.
2. 루트(arr[0])에 있는 가장 큰 값을 꺼내 배열 마지막 요소와 바꾸고 배열의 나머지 부분을 다시 힙으로 만드는 과정을 반복한다.

public class HeapSort {
  static void swap(int[] arr, int idx1, int idx2) {
    int temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
  }

  static void downHeap(int[] arr, int left, int right) {
    int temp = arr[left]; // root
    int child; // 큰 값을 갖는 자식
    int parent; // 부모

    for(parent = left; parent < (right + 1) / 2; parent = child) {
      int cl = parent * 2 + 1; // 왼쪽 자식
      int cr = cl + 1; // 오른쪽 자식
      child = (cr <= right && arr[cr] > arr[cl] ? cr : cl); // 큰 쪽을 자식에 대입

      if(temp >= arr[child]) {
        break;
      }
      arr[parent] = arr[child];
     }
     arr[parent] = temp;
  }

  static void heapSort(int[] arr) {
    // 1. 배열을 힙으로 만듬
    for(int i = (arr.length - 1)/ 2; i >= 0; i--) {
      downHeap(arr, i, arr.length - 1);
    }

    // 2. 힙 정렬을 수행
    for(int i = arr.length - 1; i > 0; i--) {
      swap(arr, 0, i); // 가장 큰 요소와 정렬되지 않은 부분의 마지막 요소를 교환
      downHeap(arr, 0, i - 1);
    }
  }

  public static void main(String[] args) {
    int[] arr = { 5, 3, 4, 1, 8, 3 };
    heapSort(arr);
  }
}

 

참고 자료

• 11강 - 힙 정렬(Heap Sort) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #11 ]