[JAVA] 힙정렬(Heap Sort) 개념과 코드 구현

힙정렬(Heap Sort)이란 힙(Heap) 자료구조를 이용한 정렬 알고리즘이다.

보통 내림차순으로 정렬할 때 최대힙을 사용하고, 오름차순으로 정렬할 때 최소힙을 사용한다.

구분	최악 시간복잡도	최선 시간복잡도	평균 시간복잡도	공간복잡도(메모리)	안정성
힙정렬	O(n log n)	O(n log n)	O(n lon n)	O(1)	N

 

* 힙(Heap)

힙은 완전 이진트리의 일종으로 최댓값 혹은 최솟값을 빠르게 찾기 위한 자료구조이다.

최대힙(Max Heap)과 최소힙(Min Heap)으로 나뉜다.

최대힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진트리이며

최소힙은 반대로 '부모의 값이 자식보다 항상 작다'는 조건을 만족하는 완전 이진트리이다.

부모 자식간의 관계는 일정하지만 형제 사이의 대소관계는 일정하지 않다.

 

힙은 배열을 이용해 구현할 수 있으며 완전 이진트리이므로 각 노드를 배열의 인덱스로 대응시킬 수 있다.

특정 노드의 인덱스를 i라고 할때 그 노드의 부모 노드는 (i-1)/2, 왼쪽 자식노드는 2i+1, 오른쪽 자식노드는 2i+2의 인덱스를 가진다.

 

알고리즘 (최소힙 기준)

1. n개의 노드에 대한 완전 이진트리를 구성한다.

2. 최소힙을 구성한다.

3. 최소힙에서 루트노트(가장 작은 값)를 꺼내 출력 배열에 추가한다.

4. 다시 최소 힙으로 만든다. 

5. 3 - 4 번의 과정을 반복하여 출력 배열의 크기와 입력 배열의 크기가 같아질때까지 반복한다.

 

소스코드

최소힙은 우선순위큐(Priority Queue)를 사용해서 구현할 수 있다.

(기본적으로 오름차순 기준으로 정렬됨. 내림차순으로 정렬할 경우  Comparator를 사용해야함)

오름차순을 기준으로 우선순위 큐를 생성하면 poll()메서드를 호출할 때마다 가장 작은 값을 반환함

public static int[] heapSort(int[] arr) {
    
    // 힙 정렬에 사용될 힙(우선순위 큐)을 선언한다.
    PriorityQueue<Integer> heap = new PriorityQueue<>();

    // 배열의 값을 힙에 모두 할당한다.(오름차순으로 정렬된다.)
    for(int i = 0; i < arr.length; i++) {
        heap.add(arr[i]);
    }

    // 힙에서 우선순위가 가장 높은 원소(root노드)를 하나씩 배열에 넣어준다.
    // 우선순위가 오름차순이므로 가장 작은 값부터 출력된다.
    for(int i = 0; i < arr.length; i++) {
        arr[i] = heap.poll();
    }

    return arr;
}