힙 정렬

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

Heap sort Idea 우선 heap의 개념부터 정리하겠습니다. Heap 완전 이진트리 형태이며, 최대 힙과 최소 힙으로 나뉜다. 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 완전 이진트리이고, 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리이다. 이러한 힙의 형태를 유지하면서 삽입과 삭제 연산이 가능하도록 해야하며, 이러한 연산을 heapify이라 한다. 힙과 이진 탐색 트리는 명확한 차이점을 가진다. 두 자료구조 모두 이진트리라는 점은 같지만, 노드 값이 다르게 구성된다. 이진 탐색 트리의 경우 가장 왼쪽의 리프노드가 가장 작고, 가장 오른쪽의 리프노드가 가장 큰 값을 가진다. 하지만 힙의 경우 부모와 자식 간의 값의 순서만 지키면 되기 때문에 차이점이 있다. Heap 표현..