준비중..
10 힙 정렬(heap sort)
# 힙 정렬
## 목차
---
1. 무엇?
2. 특징?
3. 알고리즘
## 1. 무엇?
---
최대/최소 힙 자료구조를 이용하여 정렬하는 방법. 내림차순은 max heap. 오름차순은 min heap을 사용.
1. n개의 노드에 완전 이진 트리를 구성
2. 최대 힙을 구성 - 단말 노드를 자식 노드로 가진 부모 노드부터 시작, 루트까지 올라옴.
3. 가장 큰 수를 가장 작은 수와 교환
4. 과정 2-3 을 반복
## 2. 특징?
---
- 빠름, 시간 복잡도 O(n log n)
- 추가 메모리 필요
## 3. 알고리즘
---
### 소스코드
```
public class Heap
{
private int[] element; //element[0] contains length
private static final int ROOTLOC = 1;
private static final int DEFAULT = 10;
public Heap(int size) {
if(size>DEFAULT) {element = new int[size+1]; element[0] = 0;}
else {element = new int[DEFAULT+1]; element[0] = 0;}
}
public void add(int newnum) {
if(element.length <= element[0] + 1) {
int[] elementTemp = new int[element[0]*2];
for(int x = 0; x < element[0]; x++) {
elementTemp[x] = element[x];
}
element = elementTemp;
}
element[++element[0]] = newnum;
upheap();
}
public int extractRoot() {
int extracted = element[1];
element[1] = element[element[0]--];
downheap();
return extracted;
}
public void upheap() {
int locmark = element[0];
while(locmark >= 1 && element[locmark/2] > element[locmark]) {
swap(locmark/2, locmark);
locmark /= 2;
}
}
public void downheap() {
int locmark = 1;
while(locmark * 2 <= element[0])
{
if(locmark * 2 + 1 <= element[0]) {
int small = smaller(locmark*2, locmark*2+1);
swap(locmark,small);
locmark = small;
}
else {
swap(locmark, locmark * 2);
locmark *= 2;
}
}
}
public void swap(int a, int b) {
int temp = element[a];
element[a] = element[b];
element[b] = temp;
}
public int smaller(int a, int b) {
return element[a] < element[b] ? a : b;
}
}
```