힙 정렬
힙
힙이란 완전 이진 트리의 일종이며,
여러 개의 값들 중에서 최대값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
최대 힙 기준으로 큰 키값이 상위 레벨에 있고 작은 키값이 하위 레벨에 있으며
이러한 특징으로 인해 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 이진 트리이다.
자세한 내용은 힙에 정리되어있다.
힙 정렬
힙 자료구조를 사용하여 정렬하는 알고리즘이다.
힙 정렬은 배열로 표현된 트리의 값들을 이당(삭제 및 다시 삽입)시켜 다시 배열로 정렬하는 방식으로 구현하는데,
힙 배열의 루트에서 원소를 삭제하여 줄어든 힙 배열 크기 뒤에 남는 공간에 삭제한 원소를 도로 넣음으로 정렬을 한다.
| 50 | 30 | 20 | 15 | 10 | 8 | 16 |
위는 값들이 들어간 힙과 그에 대응되는 배열을 시각적으로 표현한 것이다.
힙 정렬을 하려면 값들을 삭제해야 하는데, 힙에서의 삭제는 루트 노드에서만 이루어진다.
주의해야 할 점은, 삭제되는 값 자체는 루트 노드의 값이지만, 삭제되는 노드는 단말 노드라는 점이다.
삭제되는 노드는 단말 노드, 그 중 가장 오른쪽의 노드여야 하는데
이는 힙이 항상 완전 이진 트리를 유지해야 하기 때문이다.
힙 정렬을 할 때 삭제되는 값은 루트 노드에 있는 값(가장 큰 값)이기 때문에
루트 노드에 있는 값인 50을 먼저 삭제하고자 한다. 다만 앞서 말했듯이 힙은 완전 이진 트리의 형태를 유지해야 함으로
50의 위치를 최하위 레벨의 가장 우측 노드에 있는 값과 바꿔주고 50을 삭제한다.
50 삭제 후의 트리
| 16 | 30 | 20 | 15 | 10 | 8 |
이 때, 비어있게 된 위치에 삭제된 값을 넣으면 추가적인 공간 할당 필요 없이
가장 큰 값을 뒤 여유 공간에 위치하게 할 수 있다.
회색으로 표시된 영역은 힙 배열의 크기가 줄어든 부분이며, 더 이상 힙 배열로서의 역할을 하지 않는다.
| 16 | 30 | 20 | 15 | 10 | 8 | 50 |
이제 50을 삭제하였으니 조정을 하여 다시 힙을 만들어야 한다. 16을 그 자식 노드들과 비교하여 큰 값과 바꿔주고 필요시 이를 반복하면 된다.
| 30 | 16 | 20 | 15 | 10 | 8 | 50 |
이제 30을 삭제하고, 30을 삭제한 후의 위의 과정을 진행한 힙 배열을 다시 정렬하면 아래의 힙 배열이 나온다.
| 20 | 16 | 8 | 15 | 10 | 30 | 50 |
해당 과정을 반복해보자.
| 16 | 15 | 8 | 10 | 20 | 30 | 50 |
| 15 | 10 | 8 | 16 | 20 | 30 | 50 |
| 10 | 8 | 15 | 16 | 20 | 30 | 50 |
| 8 | 10 | 15 | 16 | 20 | 30 | 50 |
힙 정렬이 완료되어 가장 작은 값부터 큰 값까지 정렬된 것을 확인할 수 있다. 보이듯 힙 정렬은 힙 배열의 크기를 줄이면서 정렬을 하는 방식이다.
최소 힙이라 가정할 시 가장 작은 값을 삭제하는 방식으로 위 과정을 진행하면 정렬된 배열이 내림차순으로 정렬된다.
시간 복잡도
힙 정렬의 시간 복잡도는 O(nlogn)이다.
힙을 만드는데 O(n)의 시간이 걸리고, 힙을 정렬하는데 O(nlogn)의 시간이 걸리기 때문이다.
힙 정렬은 최악의 경우 O(nlogn)의 시간 복잡도를 보장하기 때문에 대규모 데이터를 정렬하는데에 효율적이다.
다만, 상수 계수가 크기 때문에 데이터의 크기가 작을 경우에는 다른 정렬 알고리즘보다 느릴 수 있다는 단점도 있다.