지난 글에서 최댓값이나 최솟값을 빠르게 찾을 수 있는 자료구조인 힙에 대해 알아보았다.
[자료구조] Heap (힙)
이번에는 Heap을 이용한 정렬 알고리즘인 Heap Sort에 대해 알아보자.
Heap Sort
힙 정렬의 아이디어는 생각보다 간단하다.
정수형 배열이 주어졌다고 가정했을 때 이를 오름차순으로 정렬하고 싶다면, Min Heap에 원소들을 차례대로 삽입한 뒤 하나씩 제거하면서 배열에 다시 쓰면 된다.
예를 들어 다음과 같이 1부터 6까지의 정수가 들어있는 배열이 있다면
첫 번째 원소인 3부터 마지막 원소인 2까지 Min Heap에 다음과 같이 넣을 수 있다.
그럼 Min Heap은 루트 노드에 항상 최솟값이 존재하므로 배열 크기 만큼 삭제 연산을 진행하여 오름차순으로 정렬된 결과를 얻을 수 있다.
그리고 정렬하는 과정에서 시간 복잡도를 계산해본다면, 처음 모든 원소에 대하여 삽입 연산을 진행하므로 O(NlogN) 만큼의 시간이 소요되고, 다시 원소 개수 만큼 삭제 연산을 하므로 O(NlogN) 만큼의 시간이 소요된다. 이로써 힙 정렬의 시간 복잡도는 O(NlogN)이라고 할 수 있다.
하지만 위와 같이 정렬을 구현하다면 힙에 대한 저장 공간이 배열 크기만큼 별도로 필요하다. 즉, 공간복잡도가 O(N)이 되는데, 별도의 저장 공간을 두지 않고도 힙 정렬을 구현할 수 있는 방법이 존재한다.
in-place Heap Sort
추가적인 저장 공간이 필요 없거나, 원소들의 개수에 비해 충분히 무시할 만큼의 저장 공간만 사용하는 정렬 알고리즘들을 in-place sort라고 한다.
힙 정렬 역시 주어진 배열을 하나의 힙으로 만들어 별도의 저장 공간 없이 정렬을 할 수 있다.
그 전에 우선 heapify라는 연산에 대해 알아볼 필요가 있다.
Heapify
heapify 연산은 index 값을 입력으로 받는데, 해당 index의 원소를 하위 자식 노드의 값과 비교하여 heap 성질을 만족하도록 해당 index 원소의 위치를 조정해주는 작업이다.
쉽게 생각하면 삭제 연산에서 마지막 원소가 루트 노드에 위치한 후 자기 위치를 찾아가는 과정과 동일하다.
시간 복잡도는 index에 따라 달라지는데 루트 노드, 즉 index가 0이라면 시간 복잡도는 삭제 연산과 동일하게 O(logN)이다.
예를 들어 다음과 같이 정렬 전의 배열을 완전 이진 트리로 만들고
0번째 index의 원소인 3에 대하여 Max Heap 성질을 만족하도록 heapify 연산을 수행하면
3의 위치를 결정해줄 수 있다.
하지만 루트 노드에 대해 heapify 연산을 수행했다고 해서 트리 전체가 heap 성질을 만족하는 것은 아니다!
위의 경우도 Max Heap을 만족하도록 heapify 연산을 수행했지만, 4보다 큰 6이 자식 노드에, 1보다 큰 2가 자식 노드에 있는 것을 확인할 수 있다.
여기서 알 수 있는 사실은, 어떤 index에 대해 heapify를 수행하고 나서 그 index를 루트 노드로 하는 트리가 heap 성질을 만족하려면, heapify를 수행하기 전 왼쪽 서브트리와 오른쪽 서브트리 모두 heap 성질을 만족해야 한다는 것이다.
따라서 위의 예시에서 트리 전체가 Max Heap 성질을 만족하기 위해선, heapify를 루트 노드인 3부터 하는 것이 아니라 bottom up 형식으로 아래 자식 노드들 부터 진행해야 한다.
또한 heapify 연산 자체가 자식 노드들과 비교하는 연산이므로 자식 노드가 없는 leaf 노드는 heapify 연산을 수행할 필요가 없다.
결론적으로 2, 1, 0 번째 index 순서로 다음과 같이 heapify 연산을 수행하면
6개 원소를 포함하는 트리 전체가 Max Heap 성질을 만족한다.
Why Max Heap?
위 예시가 이해됐다면 오름차순으로 정렬하는데 왜 Max Heap을 만드는지 의아해 할 것이다.
그 이유는 최댓값을 루트 노드를 통해 접근할 수 있기 때문이다.
오름차순으로 정렬을 한다면 최댓값은 가장 마지막 인덱스에 위치해야 한다. 따라서 Max Heap 의 0번째 인덱스인 최댓값과 마지막 인덱스의 원소를 swap 하고, heap size를 1 감소시키면 정렬이 완료된 마지막 원소를 제외하고 계속 정렬을 이어나갈 수 있다.
중요한 점은 마지막 인덱스와 swap을 하면서 heap 성질이 깨질 수 있다. 따라서 swap 이후에 루트 노드에 대해 heapify 연산을 수행하여 다시 Max Heap 성질을 만족하도록 한다.
만약 Min Heap으로 만들었다면, 최솟값을 맨 앞인 0번째 인덱스에 저장해야 하고, 1번째 인덱스부터 다시 정렬을 진행해야 하는데, in-place로 정렬하기엔 꽤나 까다롭다.
따라서 가장 뒤에 위치해야 하는 원소부터 역순으로 정렬을 하도록 오름차순일 땐 Max Heap, 내림차순일 땐 Min Heap을 구성하도록 한다.
Heap을 완성한 뒤의 과정을 다시 정리하면
- 0번째 인덱스 원소와 마지막 인덱스 원소를 swap 한다.
- heap size를 1 감소시킨다.
- 0번째 인덱스에 대해 heapify를 수행한다.
위 과정을 heap size가 1이 될 때까지 반복한다.
위 과정을 예시에 적용한다면 다음과 같이 정렬이 이루어진다.
코드 구현
heapify를 포함한 in-place sort 에 대한 코드는 다음과 같이 구현할 수 있다.
extension Array {
mutating private func heapify(index: Int, size: Int, by areIncreasingOrder: (Self.Element, Self.Element) -> Bool) {
let temp = self[index]
var parent = index
var child = 2 * parent + 1
while child < size {
if child + 1 < size && areIncreasingOrder(self[child], self[child + 1]) { child += 1 }
if !areIncreasingOrder(temp, self[child]) { break }
self[parent] = self[child]
parent = child
child = 2 * parent + 1
}
self[parent] = temp
}
mutating func heapSort(by areIncreasingOrder: (Self.Element, Self.Element) -> Bool) {
var index = (count - 1) / 2 // 자식이 존재하는 마지막 노드
while index >= 0 { // 루트 노드까지 heapify
heapify(index: index, size: count, by: areIncreasingOrder)
index -= 1
}
index = count - 1
while index >= 1 {
swapAt(0, index)
heapify(index: 0, size: index, by: areIncreasingOrder) // 루트 노드 heapify
index -= 1
}
}
}그렇다면 in-place heap sort의 시간 복잡도를 알아보자.
먼저 첫번 째 while 문인 자식이 있는 노드들에 대하여 heapify하는 과정은 O(NlogN)으로 착각할 수 있으나 O(N)이다.
직관적으로 이해가 가지 않는 게 당연한데, Talyor 급수 기반의 증명 과정을 알고 싶다면 다음 블로그 글을 참고해도 좋을 것 같다.
build heap 시간복잡도 O(n) 이해하기
그 다음 swap 과정을 통해 정렬하는 과정은 heapify가 N-1번 이루어지므로 O(NlogN)이다.
따라서 전체 시간 복잡도는 O(NlogN)으로 처음 소개한 정렬 방법과 시간 복잡도는 같다.
하지만 추가적인 메모리를 쓰지 않는다는 점에서 더 효율적이라고 할 수 있다.
마지막으로 이전 포스트와 같이 테스트 결과를 첨부하면서 글을 마치겠다.
var players = ["Azpilicueta", "Silva", "Kante", "Kovacic", "Pulisic", "Mudryk", "Sterling", "Gallagher"]
players.heapSort { $0 < $1 }
print(players)
👍🏻
Reference
https://leeminju531.tistory.com/33
