[Algorithm] Heap sort (힙정렬)

1. Heap Sort (힙정렬)

 

힙 정렬은 자료구조 중 하나인 binary heap을 활용하여 정렬하는 방법이다. 데이터를 최대 힙 또는 최소 힙으로 구성하여서 정렬을 진행하는데, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 바이너리 힙을 구성하게 되면 해당 자료구조 내에서 최소값, 또는 최대값을 알 수 있기 때문에 이 값들을 반복해서 찾아 정렬을 진행할 수 있다.

 

힙정렬을 위해서는 두가지 프로세스를 반복해야한다.

1. 바이너리 힙 구조를 만드는 과정 (heapify)
2. 힙의 root 값을 가져와 정렬된 메모리에 저장하는 과정

위의 두 과정을 트리에 남아있는 데이터가 없을 때까지 반복한다.

 

 

2. Heap Sort 구현

 

맨 처음 max heap 을 구성한다. 그 다음 N번의 반복을 통해서 root 값을 가져와 정렬하는 과정과 heapify 를 통해서 max heap 구조를 구성하는 과정을 반복한다.

 

heapify는 현재 트리의 서브 트리들이 heap 으로 구조가 되어있어야지 진행할 수 있다. 이때문에 bottom-up 순서로 서브 트리들부터 더 큰 범위의 트리 순으로 heapify를 진행한다. heapify는 부모 노드와 자식 노드들을 비교하여 더 큰 데이터를 부모 노드와 자리를 교체하는 방식으로 진행한다.

 

- Java를 이용한 Heap Sort 구현

import java.util.Arrays;
import Algorithm.Sorting.Sort;

public class HeapSort implements Sort {

    private int[] array;

    public HeapSort(int[] array) {
        this.array = Arrays.copyOf(array, array.length);
    }

    @Override
    public int[] sort() {
        // 1. max heap 생성
        buildMaxHeap(array);

        // 2. root node 추출하여 정렬 및 heapify 과정을 반복한다.
        heapSort(array);
        return array;
    }

    private int getParent(int index) {
        return (index - 1) / 2;
    }

    // parent 와 children을 비교하여 더 큰 값을 parent 값으로 하는 방식으로 heapify 진행한다.
    private void heapify(int[] array, int N, int parent) {
        int targetIdx, leftChild, rightChild;
        while(parent * 2 + 1 < N) {
            targetIdx = parent;
            leftChild = parent * 2 + 1;
            rightChild = parent * 2 + 2;

            if(leftChild < N) targetIdx = array[targetIdx] < array[leftChild] ? leftChild : targetIdx;
            if(rightChild < N) targetIdx = array[targetIdx] < array[rightChild] ? rightChild : targetIdx;
            if(targetIdx != parent) {
                int temp = array[targetIdx];
                array[targetIdx] = array[parent];
                array[parent] = temp;
                parent = targetIdx;
            } else return ;
        }
    }

    // max heap 구성
    private void buildMaxHeap(int[] array) {
        int N = array.length;

        for(int i = getParent(N - 1); -1 < i; i--) {
            heapify(array, N, i);
        }
    }

    // heap sort 진행
    private void heapSort(int[] array) {
        int N = array.length;
        for(int i = 1; i < N; i++) {
            // max 값과 array 의 i 위치에 있는 값의 자리를 바꿔 정렬한다.
            int temp = array[N - i];
            array[N - i] = array[0];
            array[0] = temp;

            // i 이후의 값들에 대해서 heapify를 통해서 가장 큰 값을 찾기 위해 heapify 를 구한다.
            heapify(array, N - i, 0);
        }
    }
    
}

 

3. Heap Sort 복잡도

- 시간 복잡도: O(N log N)

• heapify: O(log N)
• 전체 N번을 반복하기 때문에 최종 시간복잡도는 N log N이 된다.

- 공간 복잡도: O(1)

 

 

[reference]

- https://www.geeksforgeeks.org/heap-sort/

HeapSort - GeeksforGeeks

- https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC

힙 정렬 - 위키백과, 우리 모두의 백과사전