[자료구조] Heap Sort (힙 정렬)

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

개념

최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법

추가적인 메모리를 필요로 하지 않음
항상 O(n log n)정렬의 성능을 발휘
퀵정렬이 힙정렬보다 일반적으로 빠르게 동작
데이터의 순서가 바뀌는 불안정 정렬

1. 원소들을 전부 힙에 삽입
2. 힙의 루트에 있는 값은 남은 수들 중에서 최솟값(혹은 최댓값)을 가지므로 루트를 출력하고 힙에서 제거
3. 힙이 빌 때까지 2의 과정을 반복

https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-2.2.2

 

시간복잡도

(Worst Case = Best Case = Average Case)

O(n log n)

 

예제 코드

void heapify(int arr[], int n, int i)
{
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest])
  {
    largest = left;
  }

  if (right < n && arr[right] > arr[largest])
  {
    largest = right;
  }

  if (largest != i)
  {
    swap(arr[i], arr[largest]);

    heapify(arr, n, largest);
  }
}

void heapSort(int arr[], int n)
{
  for (int i = n / 2 - 1; i >= 0; --i)
  {
    heapify(arr, n, i);
  }

  for (int i = n - 1; i >= 0; --i)
  {
    swap(arr[0], arr[i]);

    heapify(arr, i, 0);
  }
}