힙 정렬은 선택 정렬(Selection Sort)과 유사하지만, 정렬되지 않은 원소들 중 최댓값(또는 최솟값)을
찾는 과정을 힙(Heap) 자료구조를 이용하여 효율적으로 수행하는 정렬 알고리즘이다.
이 알고리즘은 힙이란 특수한 트리 기반 자료구조를 활용하여 데이터를 정렬한다.
힙 정렬은 평균 및 최악의 경우에도 O(N log N)의 시간 복잡도를 가지므로 효율적인 정렬 알고리즘이다.
: 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워진다.
힙 속성
: 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같다.(정렬 시 큰 값을 먼저 추출할 때 사용)
: 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같다.(정렬 시 작은 값을 먼저 추출할 때 사용)
⇒ 힙 정렬은 이 중 최대 힙을 주로 사용한다.
힙 정렬은 크게 두 단계로 나뉜다.
: 주어진 배열을 최대 힙 구조로 만든다.
배열의 중간부터 시작하여 아래에서 위로 올라가면서 힙 속성을 만족시키도록 조정한다.