EunSung.log

힙 정렬

4 min read

개요

힙 정렬Heap Sort은 힙을 활용한 정렬 알고리즘이다. 내림차순 정렬을 위해서는 최소 힙을, 오름차순 정렬을 위해서는 최대 힙을 사용한다.

동작

  1. 최대 힙(혹은 최소 힙)을 구성한다.
  2. 힙의 루트 노드를 배열의 마지막 요소와 교환하고, 힙의 크기를 1 줄인다.
    • 힙의 특성 상, 최대/최소 힙의 루트 노드는 힙의 최대/최소값이다.
  3. 힙을 재구성한다.
  4. 힙이 빌 때까지 2, 3 과정을 반복한다.

시간 복잡도

  • 최선의 경우:
  • 최악의 경우:
  • 평균적인 경우:

분석

힙 트리는 완전 이진 트리의 일종이므로, 전체 높이는 대략 수준이다. 따라서 하나의 요소를 힙에 삽입하거나 루트 노드를 삭제한 후 힙을 재구성하는 데는 각각 최악의 경우 만큼 소요된다.

힙 정렬의 시간 복잡도는 다음과 같다.

  • 최대/최소 힙을 구성하는데 .
  • 루트 노드를 마지막 원소와 교환한 뒤 힙 크기를 줄이고 재구성하는 과정 - - 을 번 반복.
  • 따라서, 시간 복잡도는 .

특징

  • 불안정 정렬이다.
  • 제자리 정렬이다.
  • 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때 가장 유용하다.
  • 캐시 친화성이 떨어져 시간 복잡도가 똑같이 인 퀵 정렬보다 실제 성능이 느릴 수 있다.

구현

public static class HeapSort {
	public static void sort(int[] array) {
		int n = array.length;
 
		for (int i = n / 2 - 1; i >= 0; i--) {
			heapify(array, n, i);
		}
 
		for (int i = n - 1; i > 0; i--) {
			swap(array, 0, i);
			heapify(arr, i, 0);
		}
	}
 
	private static void heapify(int[] array, int heapSize, int rootIndex) {
		int largest = rootIndex;
		int leftChild = 2 * rootIndex;
		int rightChild = 2 * rootIndex + 1;
 
		if (leftChild < heapSize && array[leftChild] > array[largest])
			largest = leftChild;
		if (rightChild < heapSize && array[rightChild] > array[largest])
			largest = rightChild;
 
		if (largest != rootIndex) {
			swap(array, rootIndex, largest);
			heapify(array, heapSize, largest);
		}
	}
 
	private static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}

참고문헌

백링크