알고리즘 공부 <4> - 힙정렬

힙 정렬 (Heap Sort)

오늘은 힙 정렬이라는것을 한번 공부 해보자

힙 정렬은 우선순위에 따라 접근해야하면 정렬된 구조를 이룰때 사용하는 자료구조입니다.

힙은 한노드가 최대 두 개의 자식노드를 가지면서, 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉채워진 완전 이진트리를 기본으로 합니다.

힙 정렬을 이해하기 위해 먼저 트리의 구조를 알아야 할 필요가 있습니다. 

Perfect Binary Tree(포화 이진 트리) , Complete Binary Tree (완전 이진 트리) 이 두 구조를 먼저 잠깐 보고 갑시다.

---

Perfect Binary Tree

먼저 h는 해당 트리의 높이를 의미한다.  포화 이진 트리는 h-1 이하 레벨에서 2개의 자식노드를 가지고 있다.

Complete Binary Tree

완전이진 트리는 h-2 레벨에서는 2개의 자식 노드를 가지고 있다. 그리고 h 레벨에서는 왼쪽 부터 차오르는 형태를 말한다.

---

Heap

힙은 앞서 본 완전 이진트리를 기본으로 합니다. 그리고 각 노드의 값은 자신의 자식노드 값보다 크거나 같고 또는 각 노드의 값은 자신의 자식 노드가 가진 값보다 작거나 같습니다.

위 구조에서 X가 가장 클때 이 힙을 MAX HEAP 이라고 하며

반대로 X가 Y와Z보다 작을 때 MIN HEAP 이라고 합니다. 

우리는 MAX HEAP에 대해서 한번 알아 봅시다.

이는 앞서 설명한 내용과 동일하다.

다만 힙을 이루기전에 먼저 배열에 넣은후 이를 힙구조 하나씩 정렬한다는 점이 있다. 그렇기 때문에 입력한 배열 사이즈 >= 힙구조 사이즈 를 이룬다.

또 위의 그림에서 배열의 인덱스에 따라 각 트리 노드에 매핑이 되어진 것을 볼 수 있다.

---

Heapify

자 이제 트리 구조가 무엇이고 힙 구조가 무엇인지 알았으니 이 힙을 구성하는 과정을 살펴 보자

주어진 자료구조에서 힙 성질을 만족하도록 하는 연산을 heapify  라고 한다. 

힙 구조를 만족한 상태에서 한 인덱스 i 에 해당하는 값이 다른 값으로 변경되었는데 이 값이 힙구조를 깼다고 생각 해보자 즉

그림 과 같이 값 14와 4가 변경 된상태 서는 힙구조 깨지게된다. 이후 그림과 같은 과정을 거쳐서 다시 구성되어지는 과정을 거치게 된다.

이를 의사코드로 정리하면 위와 같다. 

그렇다면 위 그림과 같이 heapify  를 해야하는 과정을 worst 케이스의 경우에 시간 복잡도 함수를 구하면 어떻게 될까? 결과부터 말하자면

T(n) £ T(2n/3) + Q(1)  이 된다. 

먼저  n  ->  2n/3 이 되는 이유를 설명하자면  직관적으로 보게되면 위 그림에서 왼쪽 노드의 비율을 보면 11 -> 7 개수로 주는데 

이유는 7/11 =0.6

비율로  2n/3에 해당 되어진다. 

좀더 명확하게 보자면 

파란색 그림에 해당하는 노드의 총개수( 2^0 +..2^1 +...+2^h-1 )를 구하고 그리고 나머지 노드 개수를 구해서 비율을 따져보면 2:1이 나온다. 한번 해보시길 바랍니다.

즉 그리고 T(n) £ T(2n/3) + Q(1) 에 해당하는 빅오는 앞선 알고리즘 공부에서 했던것과 비슷한 형식이므로 빅오 또한 같다 즉  ,T(n) = O(lg n)  이된다.

Build Heap

다음으로 전체적으로 힙구조를 만드는 과정을 보자.  이 과정은 단순하다 아래에서 부터 위로 전부 heapify 과정을 거치면 된다. 

하지만 이런식으로 처음부터 배열에서 insert 과정을 다 거치게 된다면 빅오는  O(nlgn) 이 된다.

이를 더 줄일 수있는 방법이 있는데 리프 노드를 제외한 노드들에 대한  heapify  과정을 거치면 된다.

즉 배열에 따리 완전 이진 트리를 구성하고있는 아래그림의 경우에는 인덱스 5 부터 수행하면 된다.

위에서 설명했듯이 heapify 과정을 리프노드가 아닌것 부터 차례 대로 수행 하면 됩니다. 또 이에 해당하는 빅오를 구해야 하므로 최악의  경우를

생각해 주기 위해서 가장 오른쪽 끝 노드의 인덱스가 마지막이라고 생각하겠습니다. 위의 그림의 경우 마지막 인덱스는 15가되겠네요

즉    h = 0 의 경우는 모두 리프노드이므로 의미 가없습니다. 굳이 계산 한다면 즉 리프가 아니라고 가정한다면 15/2^1 (올림) 가 되겠네요

 h = 1 의 경우 15/2^2 의 올림인 4개의 노드가 가장 많이 heapify 과정을 거치게 됩니다. (최악의 경우)

 h = 2 의 경우 15/2^3 의 올림인 2개의 노드 가 가장 많이 heapify 과정을 거치게 됩니다. (최악의 경우)

 ...

 ...

 h= h 의 경우 15/2^h+1 의 올림일 것입니다. 

그리고 앞서 설명 했듯이 각 heapify 과정의 각 값은 O(lg n)  이다.

즉 

Heap Sort

이제 마지막으로 이러한 과정을 전부 거치는 힙 정렬 과정을 보자 

먼저 힙구조가 완성 된 상태에서 정렬의 과정을 보자

그림과 같이 있다고 할때 위에서 부터 하나씩 띄어내기 시작 할 것이다. 즉

그리고 최종으로는 전부 정렬이 된다.

이는 즉

이 된다.

자 빅오를 구해보자

우선 가장 먼저 힙을 만드는 과정은 O(n) 이 되고 이후 heapify 과정을 거치게 됩니다.

최악의 경우 가장 말단노드(리프노드가)가 루트 노드 까지 올라와야 할 경우 트리의 높이에 해당되는 lg n  까지 올라가게 될것이고 모든 노드가 이를 수행 해야 하므로 O(nlgn) 이 됩니다.  이후 딜리트 과정은 O(1) 이고 n번을 거치게 되므로 O(n) 이 된다.

따라서 힙정렬은

  O(n) + O(n) + O(nlgn) = O(nlgn)

이 됩니다.

오늘은 힙정렬에 대해 공부 해보았다 ! 부족하지만 앞으로도 열심히 공부해보자