힙 정렬 (Heap Sort)

1. 정의 🏄‍♂️

 

힙 정렬

  힙정렬이란 자료구조 힙(Heap)을 기반으로 하는 정렬 방식이다. 오름차순 정렬일 경우 최대힙을 이용하고 내림차순 정렬일 경우 최소힙을 이용한다.

  간단하게 설명하자면 힙 정렬은 루트노드를 제거하고 제거된 루트 노드를 배열의 뒷부분부터 채워 넣으면서 정렬이 이루어지는 것이다.

 

2. 동작 방식 🚣‍♂️

  최대힙을 이용하여 오름차순으로 정렬하는 경우를 생각해 보자. 가장 쉽게 생각할 수 있는 동작방식은 아래와 같다.

1. 정렬해야 하는 원소들을 하나씩 힙에 넣어준다.
2. 삭제를 하면서 루트 노드를 가져오고 그것을 배열의 뒷부분부터 채운다.

  이렇게 한다면 기존 배열로부터 힙을 구성하는 배열 하나를 추가적으로 만들고(1번 과정), 뒷부분부터 정렬된 원소들을 넣을 배열을 하나 더 만들어야 한다.(2번 과정) 그러면 총 2개의 배열을 더 만들어야 하는 문제가 있다.

  그러므로 기존의 배열에서 바로 정렬할 수 있는 방식을 알아보자. 이 방식은 Heapify 연산을 이용하여 추가 배열을 생성하지 않고 정렬한다. Heapify란 힙 생성 알고리즘으로 부모 노드의 두 자식 노드 중 크기가 더 큰 자식을 부모와 바꾸는 알고리즘이다. 동작 방식은 아래와 같다.

1. 최대 힙을 구성한다.
2. 루트 노드를 마지막 요소와 바꾼다.
3. 힙의 사이즈를 하나 줄이고 힙을 다시 구성한다.
4. 2~3 과정을 반복한다.

  일반적인 배열의 경우 0번 인덱스부터 시작하므로 부모 인덱스와 자식 인덱스의 관계를 아래와 같이 생각한다는 점을 유의하자.

부모 Index = (자식 Index) / 2 - 1
왼쪽 자식 Index = (부모 Index) * 2 + 1
오른쪽 자식 Index = (부모 Index) * 2 + 2

  '2, 1, 3, 4, 5'를 힙정렬을 이용해서 정렬해 보자. size는 5이므로 1부터 부모인덱스로 하여 최대힙을 구성한다. ( 5 / 2 - 1 = 5)(코드에서 구현된 Heapify를 참고하면 동작 방식 충분히 이해할 수 있을 것이다. 우선 그림을 통해 동작 방식을 크게 이해해 보도록 하자.)

  완성된 모습은 아래와 같다.

  그리고 루트 노드와 마지막 요소를 바꿔주고 힙을 재구성하는 동작을 반복한다. 그러면 마지막 노드부터 해서 요소들이 정렬된다. 정렬된 요소는 파란색으로 표시하였다.

  최종적으로 정렬된 모습은 아래와 같다.

 

3. 구현(JAVA) 🏊‍♂️

  다음은 구현코드이다. Heapify가 기본적으로 동작하는 방식과 사이즈를 줄여가면서 Heapify를 호출하는 방식을 유의해서 코드를 이해해 보자.

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

    heapSort(array);
}

public static void heapSort(int[] array) {
    int size = array.length;

    // 힙을 구성한다. - 동작방식(1)
    int parent = size / 2 - 1;
    for(int i = parent; i >= 0; i--) {
        heapify(array, size, i);
    }

    for(int i = size - 1; i > 0; i--) {
        // 루트노드와 마지막 요소를 바꾼다. - 동작방식(2)
        swap(array, 0, i);
        // 힙의 사이즈를 하나 줄이고 힙을 다시 구성한다. - 동작방식(3)
        heapify(array, i, 0);
    }
}

public static void heapify(int array[], int size, int current) {
    int parent = current;
    int leftChild = current * 2 + 1;
    int rightChild = current * 2 + 2;

    if(leftChild < size 
            && array[parent] < array[leftChild]) {
        parent = leftChild;
    }

    if(rightChild < size 
            && array[parent] < array[rightChild]) {
        parent = rightChild;
    }

    if(current != parent) {
        swap(array, parent, current);
        heapify(array, size, parent);
    }
}

public static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

 

4. 시간복잡도 🤽‍♂️

  Heapify를 하는데 시간복잡도는 O(log N)이다. 힙 정렬을 하는데 Heapify를 N번 호출해야 하므로 총 시간복잡도는 O(N logN)이 되게 된다.

	최선(BEST)	평균(AVERAGE)	최악(WORST)
시간복잡도	O(N logN)	O(N logN)	O(N logN)

 

해당 글은
Gyoogle님의 힙 정렬(Heap Sort),
나동빈님의 힙 정렬(Heap Sort)
을 참고하였습니다.