힙 정렬(Heap sort)

힙 정렬(Heap sort)는 최대 힙과 최소 힙을 이용해서 정렬하는 방법입니다.
N개의 자료들을 이용해서 먼저 힙을 만들고 루트를 삭제하면서 정렬합니다. 

삭제된 루트 노드의 자료를 차례대로 배열에 넣어 정렬하므로 루트 노드에 어떤 수가 들어가냐에 따라 내림차순 정렬과 오름차순 정렬이 정해집니다.
최대 힙은 루트 노드에 가장 큰 수가 들어가고, 최소 힙은 루트 노드에 가장 작은 수가 들어가기 때문에 최대 힙을 이용하면 내림차순 정렬을 최소 힙을 이용하면 오름차순 정렬을 할 수 있습니다.
(물론 루트노드 데이터를 배열에 거꾸로 넣으면 어떤 힙을 이용하든 내림차순 정렬, 오름차순 정렬 둘 다 가능합니다.) 

---

4 5 3 6 7 2 1 데이터를 이용하여 최대힙을 만들고 이를 내림차순 정렬 해보겠습니다.

 

최대 히프를 만드는 방법은 
트리의 마지막에 데이터를 넣고 
부모의 데이터가 클때까지 값을 바꾸면서 올라갑니다.

[4]

일단 데이터가 하나도 없으므로 루트 노드에 4를 넣습니다.

[5]

5를 트리의 마지막에 넣고 부모 노드와 비교하면서 부모 노드가 자신보다 작으면 서로 교체합니다.
위에서는 부모 노드인 4가 자식 노드인 5보다 작으므로 서로 바꿔줍니다.

[3]

데이터를 트리의 마지막에 넣고 부모 노드와 비교해보면 부모 노드가 자신보다 더 크므로 교체하지 않습니다.

[6]

6을 트리의 마지막에 넣고 부모와 비교해보면 부모 노드(4)가 자신(6)보다 작으므로 서로 교체합니다. 다시 비교해보면 부모 노드(5)가 자신(6)보다 또 작으므로 교체합니다.

[7]

7을 트리의 마지막에 넣고 부모가 자신 보다 클 때까지 부모 노드와 자신을 교체해가며 올라갑니다.

[2]

2를 트리의 마지막에 넣고 부모 노드와 비교해보면 부모 노드(3)가 자신(2)보다 더 크므로 교체하지 않습니다.

[1]

1을 트리의 마지막에 넣고 부모 노드와 비교해보면 부모 노드(3)가 자신(1)보다 크므로 교체하지 않습니다.

[완성된 최대 히프]

완성된 최대 힙의 모습입니다.

---

이제 최대 힙의 루트 노드 삭제를 통해 내림차순 정렬을 해봅시다. 
삭제하는 방법은 

루트 노드를 삭제한다.
삭제한 루트 노드 자리에 트리의 마지막 노드를 이동시킨다.
루트 노드를 자식 노드들 중에 큰 값과 비교하여 작은 경우 해당 자식 노드와 바꿔 주며 자식 노드들보다 클 때까지 내려간다.

입니다.

[7]

일단 루트 노드인 7을 배열에 넣고 트리의 마지막 노드인 루트에 이동시킨 뒤 자식 노드 중에서 큰 수와 비교하며 자신이 자식들보다 작으면 자식과 교체하며 내려옵니다.
1이 루트 노드로 이동.
자식들 중 큰 노드(6)과 비교했을 때 자신(1)이 작으므로 교체.
자식들 중 큰 노드(5)과 비교했을 때 자신(1)이 작으므로 교체.
삭제가 완료된 트리는 오른쪽과 같습니다.

[6]

다음 루트 노드인 6을 배열에 넣고 마찬가지로 삭제연산의 후속 처리를 해줍니다.
2가 루트 노드로 이동.
자식들 중 큰 노드(5)와 비교했을 때 자신(2)이 작으므로 교체.
자식들 중 큰 노드(4)와 비교했을 때 자신(1)이 작으므로 교체.

[5]

다음 루트 노드인 5을 배열에 넣고 마찬가지로 삭제연산의 후속 처리를 해주면 오른쪽 트리가 됩니다.
이를 트리에 노드가 존재하지 않을 때까지 반복합니다.

[4]

[3]

[2]

[1]

트리에 노드가 하나도 없으므로 힙 정렬을 종료합니다.
내림차순한 결과는 위의 배열과 같습니다.

---

최대 힙, 최소 힙을 이용한 내림차순 정렬, 오름차순 정렬의 시간 복잡도는 얼마가 될까요.
힙 정렬은 일단 N개의 자료들을 입력받아 힙을 생성합니다. 그리고 N번의 루트 노드 삭제를 통해서 정렬이 이루어집니다.
따라서 힙 생성(N x log2N) + 루트 삭제(N x log2N) 이므로 힙 정렬은 O(Nlog2N)의 시간 복잡도를 가집니다.

---

최대 힙을 이용하여 수를 입력 받고 내림차순 정렬 하는 소스코드를 작성해 보았습니다.

소스코드(배열) : https://gist.github.com/fpdjsns/38b7d28233435b30c79e6067609e3323
소스코드(우선순위 큐) : https://gist.github.com/fpdjsns/53cbaea1d0540317e90668306c93d055

실행결과