힙 정렬

힙은 우선순위 대기열에 사용하기에 매우 효율적일 뿐만 아니라

효율적인 정렬 알고리즘으로도 쓰일 수 있다.

힙에서 흥미로운 점은 힙 자체에 정렬 기능을 가지고 있다.

힙의 특성은 항상 부모 노드가 자식 노드들보다 큰 값을 가진다는 것

이것을 정렬에 활용할 수 있다.

간단히 말해서

배열의 항목들을 모두 힙에 넣은 다음 한 번에 하나씩 힙에서 가장 큰 값을 뽑아 다시 배열에 저장하면 정렬된 배열이 만들어지는 것이다.

힙의 삽입 삭제 알고리즘 모두 O(log2n)이므로 효율도 좋다

그러나 단점이 있다.

필요한 공간이 두배로 늘어난다. 대량의 자료를 정렬한다면 문제가 된다.

(옮겨야 하니까..뽑아서 옮기고 뽑아서 옮기고..)

공간 문제를 해결할 방법은 없는가?

무작위적인 자료가 담긴 배열을 힙으로 변환할 수 있다면 어떨까??(정렬전에 먼저 힙으로 만들겠다는거다 오해하지마라! 정렬이 아니다)

(그러니까 배열들을 항목들을 힙에 넣은 과정을 바로 배열을 힙으로 만들어버리겠다는것..)

1. 힙의 밑에서 두번쨰 수준의 가장 큰 값에 해당하는 색인을 찾는다

2. 그 색인에 대해 WalkDown함수를 호출한다.

3. 그 색인을 1감소 시킨다.

4. 그 색인이 0이 될떄까지 2와 3을 반복한다.

이제 무작위 배열이 힙으로 되었다면 정렬해야하는데

힙에서는 항상 제일 큰 항목이 제거되었고 제일 큰 항목을 제거하면 힙의 크기가 하나 감소되었다.

일반적인 힙에서는 제거된 항목이 필요하지 않으니 폐기하는데 힙 정렬에서는 정렬된 배열을 다시 만들어야하니까

마지막 항목과 바꾼 후 따라 내려가기 알고리즘을 적용해야한다.

바꾼후에는 그 항목을 알고리즘에서 제외시킨다