힙 정렬(Heap Sort)
27 Sep 2017 | algorithm
이번 글에서는 힙(heap)이라는 자료구조와 힙 정렬(Heap Sort) 알고리즘에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드 구현은 이곳을 참고하였습니다. 그럼 시작하겠습니다.
Heap
힙은 큰 키(우선 순위)에 자주 액세스하거나 키(우선 순위) 중심으로 정렬된 시퀀스를 활용해야 할 때 유용한 자료구조입니다. 힙은 한 노드(node)가 최대 두 개의 자식노드(child node)를 가지면서, 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 완전이진트리(complete binary tree)를 기본으로 합니다.
힙 속성(heap property)은 다음 두 가지입니다.
- heap order property : 각 노드의 값은 자신의 자식노드가 가진 값보다 크거나 같다(최대 힙, Max heap). 각 노드의 값은 자신의 자식노드가 가진 값보다 작거나 같다(최소 힙, Min heap).
- heap shape property : 모양은 완전이진트리이다. 즉 마지막 레벨의 모든 노드는 왼쪽에 쏠려 있다. (이진트리에 대해서 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다)
다음 그림이 바로 최대 힙 속성을 만족하는 자료구조입니다.
Heap vs Binary Search Tree
아래 그림은 이진탐색트리(Binary Search Tree)를 나타내고 있습니다. 힙과 이진탐색트리 모두 이진트리라는 점에서 공통점을 가지만 노드값이 다소 다르게 구성돼 있는 점을 확인할 수 있습니다. 힙은 각 노드의 값이 자식노드보다 큰 반면, 이진탐색트리는 왼쪽 자식노드가 제일 작고 부모노드가 그 다음 크며 오른쪽 자식노드가 가장 큰 값을 가집니다. 힙은 우선순위(키) 정렬에, 이진탐색트리는 탐색에 강점을 지닌 자료구조라고 합니다.
이진탐색트리와 관련해 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.
Heap을 Array로 표현
힙은 완전이진트리(complete binary tree) 성질을 만족하기 때문에 다음처럼 1차원 배열(array)로도 표현이 가능합니다.
이를 파이썬 코드로 구현하면 다음과 같습니다. 파이썬은 데이터의 인덱스가 0부터 시작합니다. 예컨대 인덱스가 2인 노드(10)의 왼쪽 자식노드(9)의 인덱스는 5, 오른쪽 자식노드(3)의 인덱스는 6이 됩니다. 어떤 노드의 인덱스를 index, 왼쪽 자식노드의 인덱스를 left_index, 오른쪽 자식노드의 인덱스를 right_index로 선언하면 다음과 같은 관계를 지닙니다.
left_index = 2 * index + 1
right_index = 2 * index + 2
하지만 글에서의 설명은 그림처럼 구성된 인덱스 기준으로 하겠습니다.
heapify
주어진 자료구조에서 힙 성질을 만족하도록 하는 연산을 heapify라고 합니다. 다음 예시와 같습니다.
먼저 4를 보겠습니다. 4는 왼쪽 자식노드 14보다 작으므로 힙 성질을 만족하지 않습니다(4는 오른쪽 자식노드 7보다도 작지만 알고리즘 구현상 왼쪽 자식노드 우선 적용). 4와 14 위치를 바꿉니다. 위치 변경 이후에도 힙 성질이 유지되는지 살펴야 합니다.
4는 새로운 왼쪽 자식노드 2보다는 크지만 오른쪽 자식노드 8보다는 작습니다. 힙 성질을 만족하지 않습니다. 4와 8 위치를 바꿉니다. 위치 변경 이후에도 힙 성질이 유지되는지 살펴야 하지만 더 이상 살필 자식노드가 없으므로 연산 수행을 종료합니다.
heapify를 파이썬으로 구현한 코드는 다음과 같습니다.
def heapify(unsorted, index, heap_size):
largest = index
left_index = 2 * index + 1
right_index = 2 * index + 2
if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
largest = left_index
if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
largest = right_index
if largest != index:
unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
heapify(unsorted, largest, heap_size)
heapify의 계산복잡성은 최악의 경우 루트노드에서 잎새노드까지 값을 비교해야 하므로 트리의 높이($h=\log_2{n}$)에 의존적입니다. 값을 비교하거나 바꾸는 연산은 $O(1)$이므로 결과적으로 heapify의 계산복잡성은 $O(\log{n})$이 됩니다.
insert
힙은 자료구조의 일종이므로 삽입 연산이 가능해야 합니다. 힙 속성 가운데 shape 속성을 만족하려면 새로운 노드는 아래 그림과 같이 마지막 레벨의 비어있는 공간 가운데 가장 왼쪽에 들어가야 할 겁니다.
예를 들어보겠습니다. 아래와 같은 힙 구조에서 18을 삽입한다고 가정해 보겠습니다. 그러면 마지막 레벨의 비어있는 공간 가운데 가장 왼쪽, 즉 5의 오른쪽 자식노드 위치에 처음 들어가게 됩니다.
하지만 18이 새로 삽입되면서 힙 속성이 깨졌습니다. heapify를 통해 맞춰 주어야 합니다. 우선 18을 부모노드인 5와 비교합니다. 위치를 바꿔 줍니다. 이번엔 16과 비교해 위치를 바꿔 줍니다. 이같이 삽입 연산을 할 때 heapify는 아래에서 위로 heapify를 해줍니다.
삽입 연산의 heapify 과정에서는 형제 노드에 대해선 값을 비교할 필요가 없습니다. 예컨대 상단 중앙그림의 마지막 레벨인 3, 18을 봅시다. 이미 힙 속성을 유지하고 있는 완전이진트리이기 때문에 기존 노드 3은 자신의 부모노드 5보다는 작거나 같다는 게 보장되어 있습니다. 따라서 18을 hepify할 때 부모노드인 5와만 비교해도 원하는 결과를 낼 수 있습니다.
그러면 삽입 연산의 계산복잡성은 얼마일까요? 삽입하는 데 드는 연산 $O(1)$, 해당 노드를 heapfy하는 데 $O(\log{n})$이 드므로, 전체적으로는 $O(\log{n})$가 됩니다.
delete
이번엔 삭제 연산을 살펴보겠습니다. 다음과 같습니다.
우리가 지우고 싶은 값이 위 힙 구조에서 18이라고 가정해 봅시다. 그러면 마지막 레벨의 마지막 값, 즉 힙을 배열로 표현했을 때 가장 마지막 값인 5를 삭제된 요소의 위치에 옮깁니다. 이후 이 5가 잎새노드에 다다르기까지 위에서 아래로 heapify를 수행합니다.
5는 왼쪽 자식노드인 16보다 큽니다. 힙 성질을 만족하지 않습니다. 둘의 위치를 바꿔줍니다. 새로운 위치의 5는 왼쪽 자식노드인 3보다 크고, 오른쪽 자식노드는 없습니다. 힙 성질을 만족합니다. 둘의 위치를 바꾸지 않고, heapify를 종료합니다.
그러면 삭제 연산의 계산복잡성은 얼마일까요? 삭제하는 데 드는 연산 $O(1)$, 배열의 마지막 노드를 삭제 위치로 옮기는 연산 $O(1)$, 해당 노드를 heapfy하는 데 드는 연산 $O(\log{n})$, 이렇게 해서 전체적으로 $O(\log{n})$가 됩니다.
build heap
이번에는 임의의 숫자들을 최대 힙으로 구성해 보도록 하겠습니다. 이러한 일련의 연산 과정을 build heap이라고 합니다. 예를 들어 다음과 같은 리스트가 주어졌다고 칩시다.
12, 30, 6, 7, 4, 13, 8, 11, 50, 24, 2, 5, 10
위 숫자들을 가지고 bulid heap을 하는 가장 단순한 방법은 비어있는 힙에 위 요소들을 차례로 insert 연산을 수행해 힙을 만들어가는 과정이 될 겁니다. 새로 삽입해야 할 노드 수가 $n$개라면 노드 하나의 insert 연산을 $n$번 반복 수행해야 합니다. 그런데 마지막 요소를 삽입할 때 힙을 이미 구성하고 있는 노드의 수는 $n-1$개일 것이므로 insert 연산의 계산복잡성은 $O(\log{n})$입니다. 따라서 이 방식의 계산복잡성은 결과적으로 $O(n\log{n})$이 됩니다.
이보다 더 줄일 수는 없을까요? 방법이 하나 있습니다. 다음 그림을 보겠습니다. 위 리스트를 가지고 완전이진트리 형태로 쭉 나열하면 하단 좌측그림과 같습니다. 여기에서 잎새노드를 가지지 않는 노드(=배열의 개수를 2로 나눈 몫을 인덱스로 하는 노드)부터 차례대로 heapify를 수행해주는 것입니다. 하단 좌측그림에서 보는 것처럼 8, 13, 4, 7 순서대로 위에서 아래로 heapify를 수행합니다.
우선 8부터 보겠습니다. 자식노드가 없으므로 heapify를 수행할 대상이 없습니다. 8에 대한 heapify를 종료합니다.
이번엔 13입니다. 13은 자식노드인 5, 10보다 크므로 힙 성질을 이미 만족하고 있습니다. 13에 대한 heapify를 종료합니다.
다음은 4입니다. 4는 왼쪽 자식노드인 24보다 작으므로 힙 성질을 만족하지 않습니다. 4와 24 위치를 바꿔 줍니다. 새로운 위치의 4는 자식노드가 없으므로 heapify를 수행할 대상이 없습니다. 4에 대한 heapify를 종료합니다.
다음은 7입니다. 7은 왼쪽 자식노드인 11보다 크고, 오른쪽 자식노드인 50보다 크므로 힙 성질을 만족하지 않습니다. 7과 50 위치를 바꿔 줍니다. 새로운 위치의 7은 자식노드가 없으므로 heapify를 수행할 대상이 없습니다. 7에 대한 heapify를 종료합니다. 이를 수행한 결과가 상단 우측 그림과 같습니다.
이번엔 6과 30을 차례대로 heapify를 수행합니다. 이를 수행한 결과는 하단 우측 그림과 같습니다.
마지막으로 루트노드를 대상으로 heapify를 수행합니다. 이를 수행한 결과는 하단 우측 그림과 같습니다.
이같은 방식의 계산복잡성을 따져 보겠습니다. 1개 노드를 heapify하는 데 필요한 계산량은 $O(\log{n})$이고, $n/2$개 노드에 대해 heapify를 수행해야 하므로 전체적으로는 $O(n\log{n})$입니다. 하지만 조금 더 생각해 볼 필요가 있습니다. 아래 그림을 보겠습니다. 모든 레벨의 모든 노드가 꽉 차 있는 정이진트리(full binary tree)에서 오른쪽 맽 끝에 해당합니다.
노드 안의 숫자들은 노드 수가 $n$개인 이진트리를 배열로 표현했을 때 인덱스를 가리킵니다. 인덱스가 $n$인 데이터는 정이진트리의 오른쪽 끝 잎새노드가 되는 셈이지요. 잎새노드에 해당하는 레벨을 $d$라고 했을 때 레벨이 $d$인 노드 수는 $n/2$개입니다. 왜냐하면 레벨 $d-1$의 오른쪽 끝 노드의 인덱스가 $n/2$이기 때문입니다. 레벨이 $d-1$인 노드의 수는 전체 노드($n$)에서 레벨 $d$에 해당하는 노드 수($n/2$)와 레벨 $d-2$에 해당하는 노드 수($n/4$)를 뺀 $n/4$개가 됩니다.
build heap의 계산복잡성은 수행 대상의 노드가 전체 트리에서 차지하는 높이, 그리고 수행 대상 노드 수에 비례합니다. 레벨 $d-1$에 해당하는 노드는 그 높이가 1(=잎새노드까지의 엣지 수)입니다. 마찬가지로 레벨 $d-2$는 2, $d-3$은 3이 되겠지요. 지금까지 말씀드린 내용을 종합해 build heap의 계산복잡성을 대략적으로 나타내면 다음과 같습니다.
\[\begin{align*}
0\cdot \frac { n }{ { 2 }^{ 1 } } &+1\cdot \frac { n }{ { 2 }^{ 2 } } +2\cdot \frac { n }{ { 2 }^{ 3 } } +3\cdot \frac { n }{ { 2 }^{ 4 } } +...\\ &=\frac { n }{ 4 } \cdot \left( 1+2\cdot \frac { 1 }{ 2 } +3\cdot \frac { 1 }{ 4 } +... \right) \\ &=\frac { n }{ 4 } \cdot c=O\left( n \right)
\end{align*}\]
지금 설명드린 방식이 비어있는 힙에 차례로 insert 연산을 수행해 힙을 만들어가는 방식보다 더 효율적임을 알 수 있습니다.
Heap sort
자, 드디어 이제 힙 정렬에 대해 살펴볼 시간입니다. 힙 정렬을 수행하기 위해서는 주어진 데이터를 가지고 우선 최대 힙을 구성해야 합니다. 우리에게 주어진 데이터가 다음과 같다고 칩시다.
unsorted = [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
Heapify의 시작점은 데이터 개수(10)의 절반에 해당하는 다섯번째 노드입니다. “각 노드의 값은 자식노드보다 크거나 같다”를 만족해야 힙 성질을 가진다고 할 수 있습니다. 다섯번째 노드(7)는 자식노드의 값(1)보다 크므로 힙 성질을 만족합니다. 따라서 더 이상의 연산이 필요 없습니다.
다음은 네번째 노드를 볼 차례입니다. 네번째 노드(14)는 왼쪽 자식노드(2), 오른쪽 자식노드(8)보다 크므로 힙 성질을 만족합니다. 따라서 더 이상의 연산이 필요 없습니다. 세번째 노드 차례입니다. 세번째 노드(10)은 왼쪽 자식노드(9), 오른쪽 자식노드(3)보다 크므로 힙 성질을 만족합니다. 따라서 더 이상의 연산이 필요 없습니다.
두번째 노드 차례입니다. 두번째 노드(4)는 왼쪽 자식노드(14)보다 작습니다. 힙 성질을 만족하지 않으므로 다음처럼 4와 14의 위치를 바꿔 줍니다.
unsorted = [16, 14, 10, 4, 7, 9, 3, 2, 8, 1]
4의 위치가 위의 그림처럼 바뀌었으니 4의 자식노드들을 좀 더 살펴보아야 합니다. 4는 오른쪽 자식노드(8)보다 작습니다. 힙 성질을 만족하지 않으므로 다음처럼 4와 8의 위치를 바꿔 줍니다.
unsorted = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
4의 위치가 위의 그림처럼 바뀌었으니 4의 자식노드들을 좀 더 살펴보아야 합니다. 그런데 4의 자식노드는 존재하지 않습니다. 이로써 두번째 노드에 대한 연산을 종료합니다. 마지막으로 첫번째 노드 차례입니다. 첫번째 노드(16)는 왼쪽 자식노드(14), 오른쪽 자식노드(10)보다 크므로 힙 성질을 만족합니다. 따라서 더 이상의 연산이 필요 없습니다.
이로써 최대 힙을 구성하는 데 성공했습니다. 최대 힙을 구성하게 되면 unsorted의 첫번째 요소(16)가 전체 요소 가운데 최댓값이 됩니다.
Heap Sort 파이썬 구현
힙 정렬의 수행 방법은 다음과 같습니다.
- 주어진 원소들로 최대 힙을 구성합니다.
- 최대 힙의 루트노드(=현재 배열의 첫번째 요소=최댓값)와 말단노드(=현재 배열의 마지막 요소)를 교환해 줍니다.
- 새 루트노드에 대해 최대 힙을 구성합니다.
- 원소의 개수만큼 2와 3을 반복 수행합니다.
이를 파이썬 코드로 구현하면 다음과 같습니다.
def heap_sort(unsorted):
n = len(unsorted)
# BUILD-MAX-HEAP (A) : 위의 1단계
# 인덱스 : (n을 2로 나눈 몫-1)~0
# 최초 힙 구성시 배열의 중간부터 시작하면
# 이진트리 성질에 의해 모든 요소값을
# 서로 한번씩 비교할 수 있게 됨 : O(n)
for i in range(n // 2 - 1, -1, -1):
heapify(unsorted, i, n)
# Recurrent (B) : 2~4단계
# 한번 힙이 구성되면 개별 노드는
# 최악의 경우에도 트리의 높이(logn)
# 만큼의 자리 이동을 하게 됨
# 이런 노드들이 n개 있으므로 : O(nlogn)
for i in range(n - 1, 0, -1):
unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
heapify(unsorted, 0, i)
return unsorted
A. BUILD-MAX-HEAP의 인덱스($i$)에 따른 정렬 과정은 다음과 같습니다. (단 여기에서 $i$는 파이썬 인덱스 기준)
$i$
data
초기값
[16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
4
[16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
3
[16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
2
[16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
1
[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
0
[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
B. Recurrent 부분의 인덱스에 따른 정렬 과정은 다음과 같습니다.
$i$
data
9
[1, 14, 10, 8, 7, 9, 3, 2, 4, 16]
8
[1, 8, 10, 4, 7, 9, 3, 2, 14, 16]
7
[2, 8, 9, 4, 7, 1, 3, 10, 14, 16]
6
[2, 8, 3, 4, 7, 1, 9, 10, 14, 16]
5
[1, 7, 3, 4, 2, 8, 9, 10, 14, 16]
4
[2, 4, 3, 1, 7, 8, 9, 10, 14, 16]
3
[1, 2, 3, 4, 7, 8, 9, 10, 14, 16]
2
[1, 2, 3, 4, 7, 8, 9, 10, 14, 16]
1
[1, 2, 3, 4, 7, 8, 9, 10, 14, 16]
Heap sort의 계산복잡성
그러면 힙 정렬의 계산복잡성을 따져보도록 하겠습니다. 우선 최초로 최대 힙을 만드는 A의 계산복잡성은 이미 살펴보았듯 $O(n)$입니다. 이번엔 힙이 구성된 상태에서 각 노드에 대해 heapify를 수행하는 B를 살펴보겠습니다. 말단 노드(최댓값)가 루트 노드에 올라오기까지 트리의 높이(데이터 수가 $n$개일 때 $h=\log_2n$)만큼 자리 이동을 해야 합니다. 이렇게 heapify를 해야 하는 노드들이 $n$개가 있으므로 B의 계산복잡성은 $O(n\log{n})$이 됩니다.
따라서 힙 정렬의 계산복잡성은 A와 B를 합친 $O(n)+O(n\log{n})$이며 결과적으로 $O(n\log{n})$이 됩니다.
이번 글에서는 힙(heap)이라는 자료구조와 힙 정렬(Heap Sort) 알고리즘에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드 구현은 이곳을 참고하였습니다. 그럼 시작하겠습니다.
Heap
힙은 큰 키(우선 순위)에 자주 액세스하거나 키(우선 순위) 중심으로 정렬된 시퀀스를 활용해야 할 때 유용한 자료구조입니다. 힙은 한 노드(node)가 최대 두 개의 자식노드(child node)를 가지면서, 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 완전이진트리(complete binary tree)를 기본으로 합니다.
힙 속성(heap property)은 다음 두 가지입니다.
- heap order property : 각 노드의 값은 자신의 자식노드가 가진 값보다 크거나 같다(최대 힙, Max heap). 각 노드의 값은 자신의 자식노드가 가진 값보다 작거나 같다(최소 힙, Min heap).
- heap shape property : 모양은 완전이진트리이다. 즉 마지막 레벨의 모든 노드는 왼쪽에 쏠려 있다. (이진트리에 대해서 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다)
다음 그림이 바로 최대 힙 속성을 만족하는 자료구조입니다.
Heap vs Binary Search Tree
아래 그림은 이진탐색트리(Binary Search Tree)를 나타내고 있습니다. 힙과 이진탐색트리 모두 이진트리라는 점에서 공통점을 가지만 노드값이 다소 다르게 구성돼 있는 점을 확인할 수 있습니다. 힙은 각 노드의 값이 자식노드보다 큰 반면, 이진탐색트리는 왼쪽 자식노드가 제일 작고 부모노드가 그 다음 크며 오른쪽 자식노드가 가장 큰 값을 가집니다. 힙은 우선순위(키) 정렬에, 이진탐색트리는 탐색에 강점을 지닌 자료구조라고 합니다.
이진탐색트리와 관련해 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.
Heap을 Array로 표현
힙은 완전이진트리(complete binary tree) 성질을 만족하기 때문에 다음처럼 1차원 배열(array)로도 표현이 가능합니다.
이를 파이썬 코드로 구현하면 다음과 같습니다. 파이썬은 데이터의 인덱스가 0부터 시작합니다. 예컨대 인덱스가 2인 노드(10)의 왼쪽 자식노드(9)의 인덱스는 5, 오른쪽 자식노드(3)의 인덱스는 6이 됩니다. 어떤 노드의 인덱스를 index, 왼쪽 자식노드의 인덱스를 left_index, 오른쪽 자식노드의 인덱스를 right_index로 선언하면 다음과 같은 관계를 지닙니다.
left_index = 2 * index + 1
right_index = 2 * index + 2
하지만 글에서의 설명은 그림처럼 구성된 인덱스 기준으로 하겠습니다.
heapify
주어진 자료구조에서 힙 성질을 만족하도록 하는 연산을 heapify라고 합니다. 다음 예시와 같습니다.
먼저 4를 보겠습니다. 4는 왼쪽 자식노드 14보다 작으므로 힙 성질을 만족하지 않습니다(4는 오른쪽 자식노드 7보다도 작지만 알고리즘 구현상 왼쪽 자식노드 우선 적용). 4와 14 위치를 바꿉니다. 위치 변경 이후에도 힙 성질이 유지되는지 살펴야 합니다.
4는 새로운 왼쪽 자식노드 2보다는 크지만 오른쪽 자식노드 8보다는 작습니다. 힙 성질을 만족하지 않습니다. 4와 8 위치를 바꿉니다. 위치 변경 이후에도 힙 성질이 유지되는지 살펴야 하지만 더 이상 살필 자식노드가 없으므로 연산 수행을 종료합니다.
heapify를 파이썬으로 구현한 코드는 다음과 같습니다.
def heapify(unsorted, index, heap_size):
largest = index
left_index = 2 * index + 1
right_index = 2 * index + 2
if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
largest = left_index
if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
largest = right_index
if largest != index:
unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
heapify(unsorted, largest, heap_size)
heapify의 계산복잡성은 최악의 경우 루트노드에서 잎새노드까지 값을 비교해야 하므로 트리의 높이($h=\log_2{n}$)에 의존적입니다. 값을 비교하거나 바꾸는 연산은 $O(1)$이므로 결과적으로 heapify의 계산복잡성은 $O(\log{n})$이 됩니다.
insert
힙은 자료구조의 일종이므로 삽입 연산이 가능해야 합니다. 힙 속성 가운데 shape 속성을 만족하려면 새로운 노드는 아래 그림과 같이 마지막 레벨의 비어있는 공간 가운데 가장 왼쪽에 들어가야 할 겁니다.
예를 들어보겠습니다. 아래와 같은 힙 구조에서 18을 삽입한다고 가정해 보겠습니다. 그러면 마지막 레벨의 비어있는 공간 가운데 가장 왼쪽, 즉 5의 오른쪽 자식노드 위치에 처음 들어가게 됩니다.
하지만 18이 새로 삽입되면서 힙 속성이 깨졌습니다. heapify를 통해 맞춰 주어야 합니다. 우선 18을 부모노드인 5와 비교합니다. 위치를 바꿔 줍니다. 이번엔 16과 비교해 위치를 바꿔 줍니다. 이같이 삽입 연산을 할 때 heapify는 아래에서 위로 heapify를 해줍니다.
삽입 연산의 heapify 과정에서는 형제 노드에 대해선 값을 비교할 필요가 없습니다. 예컨대 상단 중앙그림의 마지막 레벨인 3, 18을 봅시다. 이미 힙 속성을 유지하고 있는 완전이진트리이기 때문에 기존 노드 3은 자신의 부모노드 5보다는 작거나 같다는 게 보장되어 있습니다. 따라서 18을 hepify할 때 부모노드인 5와만 비교해도 원하는 결과를 낼 수 있습니다.
그러면 삽입 연산의 계산복잡성은 얼마일까요? 삽입하는 데 드는 연산 $O(1)$, 해당 노드를 heapfy하는 데 $O(\log{n})$이 드므로, 전체적으로는 $O(\log{n})$가 됩니다.
delete
이번엔 삭제 연산을 살펴보겠습니다. 다음과 같습니다.
우리가 지우고 싶은 값이 위 힙 구조에서 18이라고 가정해 봅시다. 그러면 마지막 레벨의 마지막 값, 즉 힙을 배열로 표현했을 때 가장 마지막 값인 5를 삭제된 요소의 위치에 옮깁니다. 이후 이 5가 잎새노드에 다다르기까지 위에서 아래로 heapify를 수행합니다.
5는 왼쪽 자식노드인 16보다 큽니다. 힙 성질을 만족하지 않습니다. 둘의 위치를 바꿔줍니다. 새로운 위치의 5는 왼쪽 자식노드인 3보다 크고, 오른쪽 자식노드는 없습니다. 힙 성질을 만족합니다. 둘의 위치를 바꾸지 않고, heapify를 종료합니다.
그러면 삭제 연산의 계산복잡성은 얼마일까요? 삭제하는 데 드는 연산 $O(1)$, 배열의 마지막 노드를 삭제 위치로 옮기는 연산 $O(1)$, 해당 노드를 heapfy하는 데 드는 연산 $O(\log{n})$, 이렇게 해서 전체적으로 $O(\log{n})$가 됩니다.
build heap
이번에는 임의의 숫자들을 최대 힙으로 구성해 보도록 하겠습니다. 이러한 일련의 연산 과정을 build heap이라고 합니다. 예를 들어 다음과 같은 리스트가 주어졌다고 칩시다.
12, 30, 6, 7, 4, 13, 8, 11, 50, 24, 2, 5, 10
위 숫자들을 가지고 bulid heap을 하는 가장 단순한 방법은 비어있는 힙에 위 요소들을 차례로 insert 연산을 수행해 힙을 만들어가는 과정이 될 겁니다. 새로 삽입해야 할 노드 수가 $n$개라면 노드 하나의 insert 연산을 $n$번 반복 수행해야 합니다. 그런데 마지막 요소를 삽입할 때 힙을 이미 구성하고 있는 노드의 수는 $n-1$개일 것이므로 insert 연산의 계산복잡성은 $O(\log{n})$입니다. 따라서 이 방식의 계산복잡성은 결과적으로 $O(n\log{n})$이 됩니다.
이보다 더 줄일 수는 없을까요? 방법이 하나 있습니다. 다음 그림을 보겠습니다. 위 리스트를 가지고 완전이진트리 형태로 쭉 나열하면 하단 좌측그림과 같습니다. 여기에서 잎새노드를 가지지 않는 노드(=배열의 개수를 2로 나눈 몫을 인덱스로 하는 노드)부터 차례대로 heapify를 수행해주는 것입니다. 하단 좌측그림에서 보는 것처럼 8, 13, 4, 7 순서대로 위에서 아래로 heapify를 수행합니다.
우선 8부터 보겠습니다. 자식노드가 없으므로 heapify를 수행할 대상이 없습니다. 8에 대한 heapify를 종료합니다.
이번엔 13입니다. 13은 자식노드인 5, 10보다 크므로 힙 성질을 이미 만족하고 있습니다. 13에 대한 heapify를 종료합니다.
다음은 4입니다. 4는 왼쪽 자식노드인 24보다 작으므로 힙 성질을 만족하지 않습니다. 4와 24 위치를 바꿔 줍니다. 새로운 위치의 4는 자식노드가 없으므로 heapify를 수행할 대상이 없습니다. 4에 대한 heapify를 종료합니다.
다음은 7입니다. 7은 왼쪽 자식노드인 11보다 크고, 오른쪽 자식노드인 50보다 크므로 힙 성질을 만족하지 않습니다. 7과 50 위치를 바꿔 줍니다. 새로운 위치의 7은 자식노드가 없으므로 heapify를 수행할 대상이 없습니다. 7에 대한 heapify를 종료합니다. 이를 수행한 결과가 상단 우측 그림과 같습니다.
이번엔 6과 30을 차례대로 heapify를 수행합니다. 이를 수행한 결과는 하단 우측 그림과 같습니다.
마지막으로 루트노드를 대상으로 heapify를 수행합니다. 이를 수행한 결과는 하단 우측 그림과 같습니다.
이같은 방식의 계산복잡성을 따져 보겠습니다. 1개 노드를 heapify하는 데 필요한 계산량은 $O(\log{n})$이고, $n/2$개 노드에 대해 heapify를 수행해야 하므로 전체적으로는 $O(n\log{n})$입니다. 하지만 조금 더 생각해 볼 필요가 있습니다. 아래 그림을 보겠습니다. 모든 레벨의 모든 노드가 꽉 차 있는 정이진트리(full binary tree)에서 오른쪽 맽 끝에 해당합니다.
노드 안의 숫자들은 노드 수가 $n$개인 이진트리를 배열로 표현했을 때 인덱스를 가리킵니다. 인덱스가 $n$인 데이터는 정이진트리의 오른쪽 끝 잎새노드가 되는 셈이지요. 잎새노드에 해당하는 레벨을 $d$라고 했을 때 레벨이 $d$인 노드 수는 $n/2$개입니다. 왜냐하면 레벨 $d-1$의 오른쪽 끝 노드의 인덱스가 $n/2$이기 때문입니다. 레벨이 $d-1$인 노드의 수는 전체 노드($n$)에서 레벨 $d$에 해당하는 노드 수($n/2$)와 레벨 $d-2$에 해당하는 노드 수($n/4$)를 뺀 $n/4$개가 됩니다.
build heap의 계산복잡성은 수행 대상의 노드가 전체 트리에서 차지하는 높이, 그리고 수행 대상 노드 수에 비례합니다. 레벨 $d-1$에 해당하는 노드는 그 높이가 1(=잎새노드까지의 엣지 수)입니다. 마찬가지로 레벨 $d-2$는 2, $d-3$은 3이 되겠지요. 지금까지 말씀드린 내용을 종합해 build heap의 계산복잡성을 대략적으로 나타내면 다음과 같습니다.
\[\begin{align*} 0\cdot \frac { n }{ { 2 }^{ 1 } } &+1\cdot \frac { n }{ { 2 }^{ 2 } } +2\cdot \frac { n }{ { 2 }^{ 3 } } +3\cdot \frac { n }{ { 2 }^{ 4 } } +...\\ &=\frac { n }{ 4 } \cdot \left( 1+2\cdot \frac { 1 }{ 2 } +3\cdot \frac { 1 }{ 4 } +... \right) \\ &=\frac { n }{ 4 } \cdot c=O\left( n \right) \end{align*}\]지금 설명드린 방식이 비어있는 힙에 차례로 insert 연산을 수행해 힙을 만들어가는 방식보다 더 효율적임을 알 수 있습니다.
Heap sort
자, 드디어 이제 힙 정렬에 대해 살펴볼 시간입니다. 힙 정렬을 수행하기 위해서는 주어진 데이터를 가지고 우선 최대 힙을 구성해야 합니다. 우리에게 주어진 데이터가 다음과 같다고 칩시다.
unsorted = [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
Heapify의 시작점은 데이터 개수(10)의 절반에 해당하는 다섯번째 노드입니다. “각 노드의 값은 자식노드보다 크거나 같다”를 만족해야 힙 성질을 가진다고 할 수 있습니다. 다섯번째 노드(7)는 자식노드의 값(1)보다 크므로 힙 성질을 만족합니다. 따라서 더 이상의 연산이 필요 없습니다.
다음은 네번째 노드를 볼 차례입니다. 네번째 노드(14)는 왼쪽 자식노드(2), 오른쪽 자식노드(8)보다 크므로 힙 성질을 만족합니다. 따라서 더 이상의 연산이 필요 없습니다. 세번째 노드 차례입니다. 세번째 노드(10)은 왼쪽 자식노드(9), 오른쪽 자식노드(3)보다 크므로 힙 성질을 만족합니다. 따라서 더 이상의 연산이 필요 없습니다.
두번째 노드 차례입니다. 두번째 노드(4)는 왼쪽 자식노드(14)보다 작습니다. 힙 성질을 만족하지 않으므로 다음처럼 4와 14의 위치를 바꿔 줍니다.
unsorted = [16, 14, 10, 4, 7, 9, 3, 2, 8, 1]
4의 위치가 위의 그림처럼 바뀌었으니 4의 자식노드들을 좀 더 살펴보아야 합니다. 4는 오른쪽 자식노드(8)보다 작습니다. 힙 성질을 만족하지 않으므로 다음처럼 4와 8의 위치를 바꿔 줍니다.
unsorted = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
4의 위치가 위의 그림처럼 바뀌었으니 4의 자식노드들을 좀 더 살펴보아야 합니다. 그런데 4의 자식노드는 존재하지 않습니다. 이로써 두번째 노드에 대한 연산을 종료합니다. 마지막으로 첫번째 노드 차례입니다. 첫번째 노드(16)는 왼쪽 자식노드(14), 오른쪽 자식노드(10)보다 크므로 힙 성질을 만족합니다. 따라서 더 이상의 연산이 필요 없습니다.
이로써 최대 힙을 구성하는 데 성공했습니다. 최대 힙을 구성하게 되면 unsorted의 첫번째 요소(16)가 전체 요소 가운데 최댓값이 됩니다.
Heap Sort 파이썬 구현
힙 정렬의 수행 방법은 다음과 같습니다.
- 주어진 원소들로 최대 힙을 구성합니다.
- 최대 힙의 루트노드(=현재 배열의 첫번째 요소=최댓값)와 말단노드(=현재 배열의 마지막 요소)를 교환해 줍니다.
- 새 루트노드에 대해 최대 힙을 구성합니다.
- 원소의 개수만큼 2와 3을 반복 수행합니다.
이를 파이썬 코드로 구현하면 다음과 같습니다.
def heap_sort(unsorted):
n = len(unsorted)
# BUILD-MAX-HEAP (A) : 위의 1단계
# 인덱스 : (n을 2로 나눈 몫-1)~0
# 최초 힙 구성시 배열의 중간부터 시작하면
# 이진트리 성질에 의해 모든 요소값을
# 서로 한번씩 비교할 수 있게 됨 : O(n)
for i in range(n // 2 - 1, -1, -1):
heapify(unsorted, i, n)
# Recurrent (B) : 2~4단계
# 한번 힙이 구성되면 개별 노드는
# 최악의 경우에도 트리의 높이(logn)
# 만큼의 자리 이동을 하게 됨
# 이런 노드들이 n개 있으므로 : O(nlogn)
for i in range(n - 1, 0, -1):
unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
heapify(unsorted, 0, i)
return unsorted
A. BUILD-MAX-HEAP의 인덱스($i$)에 따른 정렬 과정은 다음과 같습니다. (단 여기에서 $i$는 파이썬 인덱스 기준)
| $i$ | data |
|---|---|
| 초기값 | [16, 4, 10, 14, 7, 9, 3, 2, 8, 1] |
| 4 | [16, 4, 10, 14, 7, 9, 3, 2, 8, 1] |
| 3 | [16, 4, 10, 14, 7, 9, 3, 2, 8, 1] |
| 2 | [16, 4, 10, 14, 7, 9, 3, 2, 8, 1] |
| 1 | [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] |
| 0 | [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] |
B. Recurrent 부분의 인덱스에 따른 정렬 과정은 다음과 같습니다.
| $i$ | data |
|---|---|
| 9 | [1, 14, 10, 8, 7, 9, 3, 2, 4, 16] |
| 8 | [1, 8, 10, 4, 7, 9, 3, 2, 14, 16] |
| 7 | [2, 8, 9, 4, 7, 1, 3, 10, 14, 16] |
| 6 | [2, 8, 3, 4, 7, 1, 9, 10, 14, 16] |
| 5 | [1, 7, 3, 4, 2, 8, 9, 10, 14, 16] |
| 4 | [2, 4, 3, 1, 7, 8, 9, 10, 14, 16] |
| 3 | [1, 2, 3, 4, 7, 8, 9, 10, 14, 16] |
| 2 | [1, 2, 3, 4, 7, 8, 9, 10, 14, 16] |
| 1 | [1, 2, 3, 4, 7, 8, 9, 10, 14, 16] |
Heap sort의 계산복잡성
그러면 힙 정렬의 계산복잡성을 따져보도록 하겠습니다. 우선 최초로 최대 힙을 만드는 A의 계산복잡성은 이미 살펴보았듯 $O(n)$입니다. 이번엔 힙이 구성된 상태에서 각 노드에 대해 heapify를 수행하는 B를 살펴보겠습니다. 말단 노드(최댓값)가 루트 노드에 올라오기까지 트리의 높이(데이터 수가 $n$개일 때 $h=\log_2n$)만큼 자리 이동을 해야 합니다. 이렇게 heapify를 해야 하는 노드들이 $n$개가 있으므로 B의 계산복잡성은 $O(n\log{n})$이 됩니다.
따라서 힙 정렬의 계산복잡성은 A와 B를 합친 $O(n)+O(n\log{n})$이며 결과적으로 $O(n\log{n})$이 됩니다.
Comments