힙정렬(예제 추가요망)

힙 정렬(Heap sort)는 마지막 레벨을 제외한 모든 레벨이 채워진 완전이진트리의 형태를 베이스로 합니다.

힙 정렬은 우선순위 별로 접근하거나 탐색할때 유용한 키 정렬 방식 입니다.

힙은 한 노드당 최대 두개의 자식노드를 지닙니다.

힙의 주요속성은 

각 노드의 값은 자신의 자식노드보다 가진값이 크거나 같다. (max heap)

혹은 각 노드의 값은 자신의 자식노드보다 가진값이 작거나 같다. (min heap)

또한 모양은 완전이진트리이며 마지막 레벨의 노드는 좌측에 몰려있다.

힙에서의 자식노드는 부모노드에서 분기할때 작거나 같거나 크다는 조건을 수렴하며 좌측에 큰값이 들어올지 작은값이 들어올지 알 수는 없습니다.

허나 크기에 따른 우선순위가 정해져 있기에 이를 통한 정렬에 유리합니다.

힙은 그 특징상 완전이진트리에서 불가능한 삽입 연산이 가능합니다.

삽입할 대상을 좌측 최하단의 자식노드를 기점으로 위의 부모노드와 비교연산하여 조건이 만족하면 부모노드와 자리를 바꾸며 자신의 자리를 탐색후 삽입됩니다.

반대로 삭제할 경우 삭제대상의 자식노드의 마지막 레벨값을 지운위치로 올린후 자식노드들과 비교하여 위에서 아래로 순서를 바꾸며 힙정렬의 규칙이 맞아 떨어질때까지 재정렬을 시행합니다.

반대로 임의의 숫자로 힙 빌드를 시행할때는 완전이진트리형태로 우선 나열후 잎새노드를 가진  바로위의 레벨의 부모노드를 시작으로 힙 재정렬을 시행해줍니다.

자식노드들과 비교해 힙속성을 만족하게 정렬을 시행하면 됩니다.

이런방식으로 마지막 잎새 노드의 부모노드부터 루트노드까지 차례로 힙정렬을 시행해주면 됩니다.