알고리즘 6장 - 정렬 문제 : 힙 정렬(2) -

알고리즘 6장

- 정렬 문제 : 힙 정렬(2) -

 

앞 장에서 힙 정렬에 대한 개념을 알아보았다면 이번 장에서는 힙 구조를 만드는 것에 대해 중점을 두고 힙 정렬에 대해 살펴볼 것이다. 따라서 개념에 대한 부분을 보고자 하면 알고리즘 5장을 보면 될 것이다.

Max 힙 구조를 만드는 코드를 한 번 살펴보자. Max 힙 구조는 부모 노드의 값이 자식 노드의 값보다 큰 이진 트리 구조를 나타낸다. Max 힙을 만드는 방법은 위에서 밑으로 만드는 것이 아니라 밑에서 위로 만든다고 할 수 있다. 만약 위에서부터 만들게 되면 밑으로 내려갈 때 마다 Max 힙의 구조를 만족시키는지를 확인해야하지만 밑에서 만들면 밑에서 트리 구조를 만족하는지만 생각하면 되기 때문에 수행 시간에서 단축될 수 있다. 여기서 length의 1/2를 I 값으로 넣는 것은 완전 이진 트리의 구조 때문이다. 배열로 생각할 때 부모 노드와 자식 노드의 관계를 2배의 차이가 난다는 것을 알기 때문에 쉽게 이해할 것이다. Max-Heapify는 노드가 입력으로 주어졌을 때 노드의 좌 우 하위 트리들은 max-heap 특성을 유지하지만 노드의 값이 하위 트리 값보다 작거나 같아서 max-heap 특성을 만족 하지 않을 때 max-heap 특성이 유지되도록 바꾸는 연산을 말한다.

예를 들어서 보게 되자. 다음과 같은 구조의 배열이 있다고 생각하자. 이 배열을 이진 트리의 표현 방법으로 나타낼 수 있다. 우리는 이진 트리의 구조를 Max 힙 구조로 만들고 싶다. 앞에서 Max 힙을 만들 때 밑에서부터 올라가는 형태로 만든다고 했으니 그에 해당하게 시작을 해보자. 그러면 마지막 자식이 있는 부모 노드를 먼저 보게 되면 5번과 10번을 생각할 수 있다. 이 둘의 관계를 생각해보면 부모 노드가 자식 노드보다 값이 크게 된다. 이것은 Max 힙 구조를 만족한다. 그러면 넘어가고 4번 노드와 8번, 9번 노드를 생각하게 된다. 이 때 4번 노드의 값보다 8번, 9번 노드의 값이 더 크게 되고 이 중 8번 노드의 값이 더 크므로 4번 노드의 값과 8번 노드의 값이 바뀌게 된다. 그 다음으로는 오른쪽의 3번 노드와 6번, 7번 자식 노드를 비교하게 된다. 이때도 자식 노드의 값이 더 크므로 값이 바뀌게 된다. 다음으로는 2번 노드와 4번, 5번 노드를 확인하게 되고 값이 또 바뀌게 된다. 그런데 여기서 5번과 10번 노드의 관계에서 Max 힙을 만족하지 못하게 되므로 또 다시 계산을 하여 값을 바꾸어 주게 된다. 마지막으로 root 노드를 바꾸게 된다. 그런데 root 노드를 바꾸면서 또 하위 트리의 구조가 Max 힙을 만족하지 못하므로 계속 바꾸어 내려가면서 Max 힙 구조를 만족시키게 한다.

수행 시간을 보게 되면 Max-Heapify를 한번 호출 할 때 마다 O(lgn)의 시간이 걸린다. 그런데 Max-Heapify의 호출 횟수가 O(n)이므로 전체 수행시간은 O(nlgn)이 된다.

Max 힙 구조에서 최댓값을 추출하는 방법을 생각해보자. 최댓값을 얻는 것은 쉽다. root 노드에 있는 값이 바로 최댓값이기 때문이다. 하지만 이후 최댓값을 추출한 후에 남은 값들이 Max 힙 구조를 계속 만족하도록 만들어야한다. 이 때 가장 마지막에 있는 노드의 값을 root 노드로 가져온다. 이후 Max-Heapify를 통해서 다시 Max 힙 구조를 맞게 계산을 해나간다.