230621 TIL #117 힙정렬

김춘복·2023년 6월 20일

TIL 알고리즘

TIL : Today I Learned

목록 보기

117/543

230621 Today I Learned

오늘은 힙정렬에 대해 알아보고 구현해보았다.

힙(Heap)

최댓값, 최솟값을 빠르게 찾아내기 위해 고안된 완전이진트리의 자료구조.
모든 노드는 자식 노드보다 우선순위(min/max)가 높거나 같다.

완전이진트리(삽입할 때 왼쪽부터 차례대로 추가하는 이진트리) 기반의 트리형 자료구조
힙을 배열로 구성하면 다음과 같은 특징을 가진다

왼쪽 자식 인덱스 = 부모 인덱스 * 2 + 1
오른쪽 자식 인덱스 = 부모 인덱스 * 2 + 2
부모 인덱스 = (자식 인덱스 - 1) / 2
힙에 대한 자세한 내용은 이미 정리한 TIL #92 참고

이미지 출처 : wikipedia

힙정렬(Heap Sort)

힙을 기반으로 동작하는 정렬 알고리즘

오름차순을 위해선 최대힙, 내림차순을 위해선 최소힙을 구성한다.

이미지 출처 및 참고 사이트 : st-lab

과정(오름차순 기준)
먼저 주어진 배열을 최대힙이 만족하도록 만드는데, 이 단계를 Heapify라 한다.
최대힙의 루트노드에 있는 가장 큰 값을 배열의 맨 뒤로 보내고, 그 원소를 제외한 나머지 배열의 원소를 다시 최대힙을 만족하도록 재구성한다.
이 과정을 반복해 맨 뒤에 가장 큰값이 가도록해서 오름차순으로 정렬한다.
시간복잡도 : O(n log n). heapify 과정에서 O(log n)이 소요되고, n개의 원소를 다 정렬할 때까지 heapify를 반복하므로 시간복잡도는 최선, 평균, 최악 모든 경우에서 O(n log n)이다.
공간복잡도 : O(1). 주어진 배열안에서 정렬하는 제자리 정렬이므로 추가적인 메모리가 필요하지 않다.
장점 :
추가적인 메모리 공간이 필요없는 제자리 정렬이다.
시간복잡도가 항상 O(n log n)으로 보장되어 효율적이다.
단점 :
구현이 비교적 복잡하다.
불안정정렬이다.
상수계수가 다른 알고리즘에 비해 크다. 힙정렬은 힙구조를 구성하고 정렬하는 단계로 나눠져 있어 추가적인 비교와 교환 연산이 수행되어 상수계수가 크다. 그래서 정렬해야할 데이터의 크기가 작은 경우에는 시간복잡도가 같은 다른 정렬에 비해 느릴 수 있다.

java로 구현

주어진 배열을 heapify로 최대힙을 구성하도록하고, 최대값(루트노드)와 마지막 노드를 swap해 맨 뒤에 최대값을 고정시키고 다시 heapify를 수행한다.

public class A_HeapSort {

  private static void heapSort(int[] array){
    int n = array.length;

//    heapify 과정에서 에러를 막기위해 크기가 1이나 0인 경우에는 정렬할 필요가 없으므로 바로 반환한다.
    if (n < 2) return;

//    가장 마지막 요소의 부모노드부터 시작한다.
    int startIndex = (n/2) -1;
//    일반 배열을 최대힙으로 구성
    for(int i = startIndex; i >= 0; i--){
      heapify(array, n, i);
    }

    for (int i = n-1; i > 0; i--) {
//    최대힙의 루트노드와 마지막 노드를 swap
      int tmp = array[0];
      array[0] = array[i];
      array[i] = tmp;
//    다시 최대힙 속성 유지위해 heapify
      heapify(array, i, 0);
    }

  }

  private static void heapify(int[] array, int n, int i){
//    현재 트리에서 부모노드의 자식노드 인덱스를 각각 구해준다.
    int largest = i; // 최대값을 가진 노드
    int left = i * 2 + 1; // 왼쪽 자식노드
    int right = i * 2 + 2; // 오른쪽 자식 노드

//    왼쪽 자식이 힙 범위 내에 있고, 부모보다 크면 largest를 왼쪽 자식으로 변경
    if (left < n && array[left] > array[largest]){
      largest = left;
    }
//    오른쪽 자식이 힙 범위 내에 있고, 부모보다 크면 largest를 오른쪽 자식으로 변경
    if (right < n && array[right] > array[largest]){
      largest = right;
    }
//   위의 과정을 통해 가장 큰 노드가 부모노드가 아니게되면 값을 swap해준다.
    if (largest != i){
      int tmp = array[i];
      array[i] = array[largest];
      array[largest] = tmp;

//    교환된 자식노드를 부모노드로 삼은 서브트리를 검사하도록 재귀적으로 heapify를 다시 호출한다.
      heapify(array, n, largest);
    }
  }

  public static void main(String[] args) {
    Random random = new Random();
    int[] array = new int[10];
    for (int i = 0; i < array.length; i++) {
      array[i] = random.nextInt(100); // 0~99까지 정수 랜덤
    }

    System.out.print("정렬 전 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
    heapSort(array);
    System.out.print("힙정렬 후 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
  }

}

힙으로 우선순위큐를 만들어 정렬하면?

array = {1,5,2,7,3,9,10,6,8,4};
// 최소힙으로 우선순위큐 따로 할당
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

// 우선순위큐에 배열을 삽입
for(int i = 0; i < array.length; i++) {
	pq.add(array[i]);
}
// pq의 최소값부터 배열에 다시 삽입해 오름차순으로 정렬
for(int i = 0; i < array.length; i++) {
	array[i] = pq.poll();
}