힙 정렬(Heap sort)

비교정렬로서 이진트리구조를 이용한 정렬방법이다.

1. 가장 위에 위치한 루트 값이 정렬조건에서 가장 우선순위가 높은 값이 위치한다.
2. 항상 부모의 값은 자식의 값보다 정렬조건에서 우선순위가 높다.

이렇게 되면 

위와 같이 힙에 값이 들어있다고 하자. 그러면 1에 위치한 값은 정렬조건에서 우선순위가 가장 높은 값이 있어야 한다.

그리고 2의 값은 아래 위치한 노드들의 값(4)보다 우선순위가 높은 값이 위치해있어야 한다.

3의 값 또한 서브트리 값들(5)보다 우선순위가 높은 값이 위치해있어야 한다.

여기서 만들어야 하는 것은 2가지 경우이다. 

1. 힙에 값을 넣었을 때
2. 힙에서 값을 빼내었을 때

1번의 경우, 힙에 값을 넣게 되면 위 그림에서 6번 노드가 새로 추가 되었다. 가장 마지막에 값을 위치시키고, 바로 위의 부모와 비교를 하여 6번의 값이 우선순위가 높은 경우에 부모의 값과 바꿔주고, 과정을 반복한다. 아닌 경우 과정을 멈춘다. 

2번의 경우, 힙에서 값을 꺼낸다. 그러면 1번 노드(루트)를 꺼내게 된다. 그리고 루트와 마지막에 위치한 노드를 변경한다.

그리고 6번 노드의 자식인 2번과 3번노드를 비교하여 우선순위가 높은 노드와 변경해준다. 이때 2번과 3번을 비교하여 더 우선순위가 높은 값을 올려준다. 

만약 값이 더이상 없는 경우 과정을 멈춘다.

이렇게 정렬하고 싶은 데이터를 모두 넣고 차례대로 꺼내어 배열에 순서대로 넣어주게 되면 정렬을 할 수 있다.

최소힙구현 코드를 참고하면 된다.

http://wondy1128.tistory.com/211?category=679868