#017_자료구조와 알고리즘_Heap 정렬

안녕하세요 삽잡이입니다.

이버 시간에는 Heap 정렬에 대해서 간략하게 설명하려고 합니다.

Heap 정렬은 Heap 트리를 이용한 정렬입니다.

Heap 트리는 완전 이진 트리로 최대 힙과 최소 힙을 가지고 있습니다.

최대 힙은 당연하게도 자식보다 부모의 값이 더 크겠지요. 최소 힙은 그와 반대이겠구요...

즉, 최대 힙같은 경우에 맨 상단에 있는 겂이 최대 값이 되겠습니다.

반대로 가장 끝에 있는 것이 최소 값이 되겠지요...

힙 트리의 경우 완전 이진 트리인 특징을 가지고 있습니다. 또한, 배열로 표현할 수 있어야합니다.

여기서 생각해볼 것은 완전 이진트리를 배열로 표현하는 것입니다.

완전 이진트리를 배열로 나타내기 위해 정규식으로 표현해보겠습니다.

왼쪽 자식 노드 = 2*x + 1

오른쪽 자식 노드 = 2*x + 2

부모 노드 = ((x -1) / 2)

이와 같은 식을 통해 완전 이진 트리를 배열로 만들 수 있습니다.

이처럼, 나의 인덱스 값을 알았을 때 부모, 자식들의 인덱스 값을 계산할 수 있게 됩니다.

index 0은 Root가 될 것이고 index 1은 왼쪽 자식, index 2는 오른쪽 자식 ... 

차례대로 배열에 트리의 노드들이 저장되는 것을 확인하실 수 있습니다.

만약, 편향적인 트리를 배열로 표현하고자 한다면, 

중간 중간 비어있는 공간들이 너무 많이 있게 되어 공간 활용도가 현저하게 떨어지니 

완전 이진 트리에서만 배열로 사용하시길 바랍니다.

그렇다면 이제 본격적으로 힙 정렬에 대해서 생각해보도록 하겠습니다.

7 2 9 4 8 3 16 17 11 5 6 이와 같은 자료를 정렬한다고 해보죠...

우선, 힙 정렬을 시작하게 된다면 초기 힙을 생성해야합니다.

위의 자료를 가지고 초기힙을 만드는 것입니다.

정렬처럼 어울리는 자리를 찾게 해줍니다. 

자... 이와 같은 자료들이 정리 되어있다면, 하나씩 꺼내서 초기 힙을 생성하는 것입니다.

노드에 자식 노드로 하나씩 추가하게 해주는데 

부모보다 자식이 크게 된다면, 위치를 바꾸면 됩니다.

 

 

이처럼 수정을 하는 것이지요... 이러한 과정을 거쳐 초기힙을 생성하게 됩니다.

초기힙을 생성하게되면 자연스레 가장 상단의 노드에는 최대 힙이 들어있을 것입니다.

그 최대 힙과 가장 말단에 있는 최소 힙의 위치를 변경해줍니다. 

그리고 가장 밑단으로 옮긴 최대 힙을 빼버린 뒤에 

최소 힙이 부모보다 작은 곳으로 값을 비교해가며 위치시킵니다.

정리하자면,

Root와 마지막 node를 교환하는 것입니다. 교환 뒤에 자료 개수를 하나 감소 시키고요...

또 같은 과정을 거치게 되며 남아 있는 값이 1이 될때까지 반복하는 것이지요...

최대 힙과 최소 힙을 교환한 뒤 최대 힙을 빼버리고 최소힙은 또 어울리는 위치에 집어넣고...

자연스레 최대 힙이 차례대로 보관되어 정렬이 완료된 상태과 되면 힙 정렬이 끝나게 됩니다.

병합정렬, 기수 정렬과 달리 추가적인 메모리가 필요 없는 장점이 있습니다.

별도의 메모리를 사용하지 않으면서 전달 받은 메모리 내에서 정렬해야한다...

또한, 언제나 평균적인 속도를 보장할 필요성이 있다면, 바로 힙 정렬을 사용하면 됩니다.

이상 힙정렬에 대해서 알아봤습니다.

지금까지 삽잡이였습니다~!