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

수영·2022년 10월 30일

알고리즘

목록 보기

11/14

힙 정렬을 하려면 먼저 힙이 무엇인지부터 알아야겠죠?!

힙(Heap)은 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조를 말합니다. 최댓값이나 최솟값을 빠르게 찾아내도록 만들어졌으며, 반정렬 상태(느슨한 정렬 상태)를 유지한다는 것이 특징입니다.

📍 힙의 두 가지 종류인 최소 힙과 최대 힙, 그리고 힙의 삽입과 삭제 등의 구현을 더 자세히 알고 싶다면 여기를 클릭하세요!

그렇다면 힙 정렬이란 무엇일까요?

힙 정렬은 이름에서도 알 수 있듯, 최소 힙 혹은 최대 힙을 사용하여 정렬하는 방법입니다.

내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 됩니다.

정렬해야 할 N개의 요소들로 최대 힙 혹은 최소 힙을 만듭니다.
➡ 내림차순 정렬을 위해서 최대 힙을 구성하면, 가장 큰 값이 루트 노드에 오게 됩니다.
➡ 반대로 오름차순 정렬을 위해서 최소 힙을 구성하면, 가장 작은 값이 루트 노드에 오게 됩니다.
힙 구성이 끝나면, 한 번에 하나씩 최댓값 혹은 최솟값을 힙에서 꺼냅니다.
➡ 값이 꺼내지면, 남은 값들은 다시 최대 힙 혹은 최소 힙에 맞게 구조화됩니다.
삭제되는 요소들은 값이 증가하는, 혹은 감소되는 순서로 정렬되게 됩니다.

👇아래와 같은 최대 힙을 통하여 정렬을 해봅시다!

👇 제일 먼저 루트에 있는 16을 정렬해줍니다.

👇 16을 빼고 난 뒤 최대 힙을 다시 재구성해주면 아래와 같은 모습이 됩니다. 남은 값들 중 가장 큰 값을 가지는 14를 16 앞에 정렬해줍니다.

👇 10을 빼고 난 뒤 최대 힙을 다시 재구성해주면 아래와 같은 모습이 됩니다. 남은 값들 중 가장 큰 값을 가지는 10를 14 앞에 정렬해줍니다.

👇 이런 식으로 계속해서 힙을 구성하다보면, 아래와 같이 모든 수들이 잘 정렬되는 것을 확인할 수 있습니다.

$O(NlogN)$

힙 트리의 전체 높이는 거의 $logN$ 입니다.
따라서, 하나의 요소를 힙에 삽입하거나 삭제할 때 heapify하는 시간은 $logN$ 만큼 소요됩니다.
정렬해야 하는 요소의 개수는 $N$ 개이기 때문에 힙 정렬은 $O(NlogN)$ 의 시간이 걸린다고 할 수 있습니다.