[알고리즘] 힙 정렬(Heap Sort)

힙 정렬

최대 힙 트리나 최소 힙 트리를 구성해 정렬

내림차순 정렬을 위해서는 최대 힙을 구성

오름차순 정렬을 위해서는 최소 힙을 구성

 

오름차순의 힙정렬을 하고 싶다면

정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만듬

최대 힙이므로 최상위 루트 노드가 가장 큰 값의 노드

가장 말단 노드가 가장 작은 값의 노드이다

 

최상위 루트 노드와 말단 노드를 교환하고 다시 힙 구조로 재배열 하는 형식!!