[Algorithms] Heap sort(힙 정렬)란 무엇인가요?
* 2020년 4월 29일 자 포스트를 업데이트한 포스트입니다.
*포스트 난이도: HOO_Junior
# Heap Sort: 쌓여있는 데이터를 정렬하는 방법
Heap이란 단어를 영어사전에서 찾아보면 "쌓여있는", "더미" 등의 뜻을 확인할 수 있다. 즉, Heap sort (힙 정렬)는 많은 양의 데이터를 정렬하는 방법이다. Heap sort는 알고리즘에서 여러 가지 정렬 방법 중 하나로, 데이터 값을 최댓값 또는 최솟값 기준으로 정렬할 때 사용한다. 최댓값 또는 최솟값으로 정렬하는 것을 한국어로는 힙 정렬(Heap sort)이라고 하며, 오름차순 또는 내림차순으로도 표현할 수 있다. Heap sort는 다른 정렬 방법과 달리 시각적으로 표현할 때 트리 형태로 나타낼 수 있다. 1차원 배열 형태에서 정렬하는 과정을 설명하기 어렵기 때문에 트리 형태로 표현해 정렬 과정을 보여준다. Heap sort를 시각적으로 표현할 때 주로 Tree 형태를 사용한다 (Figure 1). 나무에서 여러 갈래의 가지가 뻗어 나온 모양을 떠올리면 이해하기 쉽다. 제일 꼭대기의 값을 Root라 부르며, 이는 "뿌리" 또는 "근원"이라는 뜻이다. Root를 시작으로 다양한 가지가 뻗어 나온 모습을 상상하면 된다.
# Binary Tree 형태를 가진 Heap Sort
Heap sort는 Binary Tree 형태를 기반으로 동작한다. Binary Tree는 "2진법" 또는 "두 개의"라는 뜻을 가지며, 두 개의 가지로만 계속해서 뻗어나가는 나무의 형태를 말한다. 위의 Figure 1의 t1과 t2를 살펴보면 차이점을 확인할 수 있다. t1은 마지막에 값이 세 개이고, t2는 네 개다. t1은 마지막에 값이 세 개이므로 홀수 형태의 트리를 나타내고, t2는 마지막에 값이 네 개이므로 짝수 형태의 트리를 나타낸다. t1의 트리 형태를 살펴보면, 맨 위에 있는 값이 세 개이고, t2는 네 개이므로 짝수 형태의 트리를 나타낸다. t1의 트리 형태를 살펴보면, 맨 위에 있는 값이 세 개이므로 홀수 형태의 트리를 나타내고, t2는 마지막에 값이 네 개이므로 짝수 형태의 트리를 나타낸다.
# Heap Sort 언제 쓰나요?
Heap sort를 배우는데 있어서 가장 중요한 점이라고 생각하는 부분은 "언제 쓰냐는 것이다." 당연히 코딩 테스트를 할 때 무조건 나오는 Sort 알고리즘 중에 하나이기 때문에 취업할 때 물어볼 것이다. 취업에 있어서 Sort 알고리즘을 당연시하게 물어본다는 것 자체가 언제 쓰는지 알아볼 필요도 없이 정말 기본적으로 많이 쓴다는 걸 알 수 있다.
앞서서 이야기를 나눴듯이, Heap sort는 Binary Tree 형태를 기반으로 동작하기 때문에 효율성을 높인 정렬 알고리즘이다. 그렇다보니 큰 데이터셋을 정렬하거나 우선순위 큐를 구현하거나 스트리밍 데이터를 처리하는 등의 작업에 유용하지만 안정성은 보장되지 않을 수 있다는 단점을 가지고 있다. 따라서 메모리 사용량이 적고 성능이 뛰어나므로 많은 상황에서 유용하게 활용된다. 대표적으로 아래와 같은 경우에 사용이 가능하다.
- 큰 데이터셋 정렬
- 우선순위 큐 구현
- 실시간 처리
- 자원 제약 시스템
- 오프라인 데이터 분석
# 간단한 Heap Sort 예제
아래의 예제코드는 Heap sort가 어떻게 이뤄지는 지를 살펴볼 수 있다. 입력된 숫자들이 Heap sort를 통해서 어떻게 변경되는지 산출된 값을 통해서 확인이 가능하다. 또한 Heap sort를 사용하고 싶을 때 코드를 어떻게 작성해야 하는지를 아래의 기본 코드를 통해서 응용해 볼 수 있다.
def heapify(arr, n, i):
largest = i # Initialize largest as root
left = 2 * i + 1 # Left child
right = 2 * i + 2 # Right child
# Check if left child exists and is greater than the root
if left < n and arr[left] > arr[largest]:
largest = left
# Check if right child exists and is greater than the current largest
if right < n and arr[right] > arr[largest]:
largest = right
# If the largest is not the root, swap and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # Swap
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Build a max heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements from the heap
for i in range(n - 1, 0, -1):
# Move current root to end
arr[0], arr[i] = arr[i], arr[0]
# Call max heapify on the reduced heap
heapify(arr, i, 0)
# Example usage
if __name__ == "__main__":
arr = [12, 11, 13, 5, 6, 7]
print("Original array:", arr)
heap_sort(arr)
print("Sorted array:", arr)