알고리즘 5장 - 정렬 문제 : 힙 정렬(1) -

알고리즘 5장

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

 

힙 정렬은 힙 구조의 특성을 이용한 정렬이다. 수행 시간은 작은 형태로 쪼개는 합병 정렬 방법의 수행시간인 O(nlgn)과 동일하고 삽입 정렬과 동일한 제자리 정렬을 한다. 힙의 형태는 완전 이진 트리에 가까운 형태이다. 트리의 형태는 부모 노드와 자식 노드로 이루어져 있는데 부모 노드는 상위에 있는 성분이고 자식 노드는 부모 노드에 연결된 성분을 의미한다. 이는 맨 처음에 존재하는 노드를 제외하고 모든 성분은 부모 노드가 되면서 자식 노드가 될 수 있다. 이진 트리의 경우 각 부모 노드에 연결된 자식 노드의 수가 2이하인 경우를 의미하고 완전 이진 트리는 맨 처음 노드인 Root 노드부터 제일 마지막 노드인 Leaf 노드까지 빠짐없이 채워져 있는 트리를 의미한다. 또한 이렇게 채울 때 왼쪽에서 먼저 채워져야 한다. 왼쪽 노드의 끝이 차여져 있지 않은데 오른쪽이 먼저 차여지게 되면 완전 이진 트리가 아니게 된다.

 

힙 구조를 만족하는 2가지의 힙 형태가 존재하는데 최대힙 특성(Max-Heap Property)과 최소힙 특성(Min-Heap Property)이 있다. 최대힙 특성은 부모 노드의 값은 항상 자식 노드의 값보다 크다는 것을 말한다. 따라서 전체 트리의 Root 노드의 값이 가장 크다. 또한 각 하위 트리 구조의 부모 노드들은 자신의 자식 노드들의 값보다 크게 된다. 최소힙 특성은 최대힙과 반대라고 생각하면 된다. 자식 노드의 값은 항상 부모 노드의 값보다 크다. 따라서 전체 트리의 Root 노드 값이 가장 작다. 이런 특성들은 정렬을 할 때 중요한 요인으로 작용할 수 있다.

 

힙의 배열 저장 방식은 Root 노드는 배열의 첫 번째 A[1] 에 저장한다. 각각의 노드들은 레벨별로 저장을 하게 된다. 부모 노드와 자식 노드의 배열에서 index 값은 2배 차이가 나게 된다. I index를 가지는 부모 노드에서 자식 노드는 2*i와 2*i+1 노드가 자식 노드의 index가 되게 된다. 이는 완전 이진 트리의 특성으로 그렇게 될 수 있다. 이진 트리 이므로 2의 배수대로 자식 노드들이 나타나기 때문이다. 또한 완전 이진 트리이므로 왼쪽부터 채워지므로 2의 배수가 아닌 값을 가질 수가 없게 된다.

 

노드의 높이는 현재 노드에서 leaf 노드까지 내려갈 때 가장 단순하게 내려가는 가장 긴 경로에서 거쳐야 하는 간선의 수를 의미한다. 노드의 높이를 알아야하는 이유는 이를 통해 수행 시간을 알 수 있기 때문이다. 힙은 완전 이진 트리 구조를 가지기 때문에 각 레벨마다 노드의 수가 2배씩 증가하므로 높이는 (lgn)으로 나타낼 수 있다. 이는 수행 시간과 동일하게 된다.

 

Max-Heapify는 노드가 입력으로 주어졌을 때 노드의 좌 우 하위 트리들은 max-heap 특성을 유지하지만 노드의 값이 하위 트리 값보다 작거나 같아서 max-heap 특성을 만족 하지 않을 때 max-heap 특성이 유지되도록 바꾸는 연산을 말한다. 주어진 노드의 값을 흘러내리게 해서 주어진 노드와 하위 트리가 max-heap 특성을 가질 수 있도록 변형시켜주게 된다.