힙 정렬(Heap sort)

1. 힙 정렬(Heap sort)

완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기본으로하는 정렬.

불안정 정렬(unstable sort)에 속하며 평균, 최선, 최악 시간 복잡도 모두 O(n log n)임. 가장 크거나 작은 값을 구할 때 유용 

완전 이진 트리(complete binary tree)?
이진 트리의 한 종류로서 왼쪽 부터 차례대로 노드를 삽입하는 트리(왼쪽부터 채움, 왼쪽이 비어있는데 오른쪽이 채워져있을 수 없음)

https://en.wikipedia.org/wiki/Heapsort

https://commons.wikimedia.org/wiki/File:Heap_sort_example.gif

 

Java 구현 코드

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

  for (int i = n/2-1; i >= 0; i--) {
  	// 최초 heap 구성
 	heapify(arr, n, i);
  }

  for (int i = n-1; i > 0; i--) {
  	// 최대 원소를 맨 끝에 정렬하고 다시 heap구성하는 과정
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
  }
}

static void heapify(int[] arr, int n, int i) {
  int p = i;
  int l = i * 2 + 1;	// 왼쪽 자식노드
  int r = i * 2 + 2;	// 오른쪽 자식노드

  if(l < n && arr[p] < arr[l]) {
  	p = l;
  }

  if(r < n && arr[p] < arr[r]) {
  	p = r;
  }
 
  // 부모노드보다 자식노드가 더 클 경우 swap
  if(i != p) {
    int temp = arr[p];
    arr[p] = arr[i];
    arr[i] = temp;

    heapify(arr, n, p);
  }
}