[Algorithm] Heap sort

완전 이진 트리[Complete binary tree]

힙[Heap]은 완전 이진 트리[Complete binary tree]를 기본으로 한 자료구조 이다. 

또한 힙은 최댓값과 최소값을 빠르게 찾을 수 있도록 만들어진 구조이다.

완전 이진 트리

 

마지막 레벨을 제외한 노드의 자식 노드가 2개씩 있는 트리이다.

리스트로 이진트리 구현.

힙 정렬[Heap sort]

힙 정렬[위키백과]

최대 힙 정렬

1. 완전 이진 트리를 구성한다.
2. 최대 힙을 구성한다.
   1. n개의 요소들을 힙에 추가하며 부모 노드와 비교하고, 부모 노드보다 크다면 서로 위치를 바꾼다.
3. 루트 노드를 꺼내며 요소들을 정렬한다. 
   1. 루트 노드[root node] 즉, 가장 큰 노드이며, 리스트의 첫 번째 노드를 꺼낸다. 
   2. 루트 노드의 자리에 리스트의 마지막 노드를 채워 넣는다.
4. 2번과 3번을 반복한다.

힙 정렬의 장점

• 시간 복잡도가 $O(nlogn)$이며 낮은 편이다. 

 

참고

• 힙 정렬[위키백과]
• 힙 정렬이란[heejeong Kwon, git블로그]
• 힙 정렬[AndroidTeacher,Tistiry]