힙 정렬(Heap Sort) 이란?

힙 정렬은 선택 정렬(Selection Sort)과 유사하지만, 정렬되지 않은 원소들 중 최댓값(또는 최솟값)을

찾는 과정을 힙(Heap) 자료구조를 이용하여 효율적으로 수행하는 정렬 알고리즘이다.

이 알고리즘은 힙이란 특수한 트리 기반 자료구조를 활용하여 데이터를 정렬한다.

힙 정렬은 평균 및 최악의 경우에도 O(N log N)의 시간 복잡도를 가지므로 효율적인 정렬 알고리즘이다.

힙의 특징

: 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워진다.

⇒ 힙 정렬은 이 중 최대 힙을 주로 사용한다.

힙 정렬 동작 방식

힙 정렬은 크게 두 단계로 나뉜다.

  1. 힙 구성(Heapify)

: 주어진 배열을 최대 힙 구조로 만든다.

배열의 중간부터 시작하여 아래에서 위로 올라가면서 힙 속성을 만족시키도록 조정한다.