heap sort

1. Heap 이란?

• 우선순위 큐, 즉 최대값 또는 최솟값을 빠르게 찾기위해 고안된 자료구조
• 완전 이진 트리(complete binary tree)를 이용한다.
• 부모노드는 자식노드보다 항상 우선순위가 높다.
• 힙의 시간복잡도는 이진트리의 속성에 의해 O(logN)이 된다.

** 이진트리의 속성
트리의 높이(H)가 1이면 노드의 개수(N)는 1개
H=2 이면 N = 2, 3
H=3 이면 N = 4, 5, 6, 7
H=h 이면 N = 2^(h-1) ~ 2^h - 1
따라서 아래 식이 성립한다.
2^(h-1) <= n <= 2^h - 1
이를 정리하면
log(n+1) <= h <= log(n) +1 이고
우항은 h <= log(n) + 1 < log(n+1) + 1 을 성립한다.
따라서 h = log(n+1) => O(log(n))

2. Heap의 삽입과 삭제

1. 삽입 (insert)

   1. 추가할 원소를 heap 맨 끝에 넣는다.
   2. upheap 과정을 통해 이 원소의 제자리를 찾는다. (비교 및 교환 과정)

2. 삭제(pop)

   1. 루트에 있는 우선순위가 가장 높은 원소를 pop 한다.
   2. 그 자리에 가장 마지막에 위치한 원소를 위치시킨다.
   3. downHeap 과정을 통해 이 원소의 제자리를 찾는다. (비교 및 교환 과정)

3. heap 정렬

heap은 일반적으로 오름차순 정렬 구현시, 단순하게 최소힙에서 원소를 하나씩 빼서 오름차순 정렬을 구현할 수 있다고 생각할 수 있다.
하지만 최대힙을 이용하면 제자리 정렬인 heap 정렬을 구현할 수 있다.

1. 최대힙에서 루트의 원소와 가장 마지막 원소를 교환한다. (이는 곧 가장 큰 원소를 정렬된 제 위치에 위치시킨 것이다.)
2. 루트에 위치된 원소를 downHeap을 통해 heap 구조를 복원한다.
3. 루트의 원소와 맨 마지막 앞의 원소와 교환한다. (1 반복)

시간복잡도는 두 경우 모두 O(nlog(n)) 이다.