1. 힙 정렬이란?
힙 정렬(Heap Sort)은 완전 이진 트리(Complete Binary Tree) 구조를 활용하여 데이터를 정렬하는 알고리즘이다. 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 구성하여 요소를 정렬하는 방식으로 동작하며, 최악의 경우에도 O(n log n)의 시간 복잡도를 유지하는 것이 특징이다.
힙(Heap): 부모 노드가 자식 노드보다 크거나(최대 힙) 작도록(최소 힙) 유지되는 이진 트리 구조
2. 힙 정렬의 원리
힙 정렬은 '힙에서 최댓값은 루트에 위치한다'(최대 힙)라는 특징을 이용하여 정렬하는 알고리즘으로, 구체적으로 다음과 같은 작업을 반복한다.
- 루트를 꺼낸다.
- 마지막 원소(가장 하단의 오른쪽에 위치한 원소)를 루트로 이동한다.
- 루트에서 시작하여 자신보다 값이 큰 자식과 자리를 바꾸고 아래쪽으로 내려가는 작업을 반복한다. 자식의 값이 작거나 리프의 위치에 도달하면 종료한다.
3. 힙 정렬 구현
3.1 힙 정렬 알고리즘 알아보기
i값을n-1로 초기화한다.a[0]과a[i]를 교환한다.a[0], a[1], ..., a[i-1]을 힙으로 만든다.i값을 1씩 감소시켜 0이 되면 종료한다. 그렇지 않으면 2번 과정으로 돌아간다.
여기에서 n값은 배열의 원소 수이고, i값은 배열의 마지막 인덱스다. 이 때 중요한 것은 배열의 처음 상태가 힙의 요구 사항을 만족하지 않을 수도 있다는 것이다. 따라서 이 순서를 적용하기 전에 배열을 반드시 힙으로 만들어야 한다.
배열을 힙으로 만들려면?
가장 아랫부분의 작은 서브트리부터 상향식(bottom-up)으로 진행하여 전체 배열을 힙으로 만들 수 있다. 먼저 가장 아랫부분의 오른쪽 서브트리의 힙을 만들고, 같은 단계에 있는 왼쪽 서브트리로 진행한다. 그 단계를 완료하면 한 단계 위로 이동하면서 각각의 서브트리를 힙으로 만든다.
3.1 힙을 구성하는 함수
from typing import MutableSequence
def heapify(a: MutableSequence, n: int, i: int) -> None:
"""
힙 속성을 유지하도록 배열을 재구성하는 함수
- a: 정렬할 리스트
- n: 리스트의 크기
- i: 부모 노드의 인덱스
"""
largest = i # 부모 노드
left = 2 * i + 1 # 왼쪽 자식 노드
right = 2 * i + 2 # 오른쪽 자식 노드
# 왼쪽 자식 노드가 부모보다 크다면 교체
if left < n and a[left] > a[largest]:
largest = left
# 오른쪽 자식 노드가 부모보다 크다면 교체
if right < n and a[right] > a[largest]:
largest = right
# 바뀐 자식 노드 위치에서 다시 힙 속성을 확인한다 (재귀 호출)
if largest != i:
a[i], a[largest] = a[largest], a[i]
heapify(a, n, largest)✔ heapify 함수는 특정 노드를 루트로 하는 서브트리를 최대 힙으로 변환하는 역할을 한다.
✔ 부모 노드가 자식 노드보다 작다면 자리를 교환하고 재귀적으로 호출하여 힙 속성을 유지한다.
3.2 힙 정렬 함수
def heap_sort(a: MutableSequence) -> None:
"""
힙 정렬을 수행하는 함수
- a: 정렬할 리스트
"""
n = len(a)
# 최대 힙 구성
for i in range(n // 2 - 1, -1, -1):
heapify(a, n, i)
# 정렬 과정 (힙에서 요소 하나씩 제거)
for i in range(n - 1, 0, -1):
a[i], a[0] = a[0], a[i] # 최댓값(루트)을 리스트의 끝으로 이동
heapify(a, i, 0) # 줄어든 크기에 대해 다시 힙 정렬✔ heap_sort 함수는 최대 힙을 구성한 후, 루트(최댓값)를 하나씩 꺼내어 정렬하는 방식으로 동작한다.
✔ 제자리 정렬(In-place Sort)이므로 추가적인 배열을 사용하지 않는다.
4. heapq 모듈을 사용하는 힙 정렬
파이썬의 heapq 모듈은 힙에 원소를 추가하는 heappush() 함수와 힙에서 원소를 제거하는 heappop() 함수를 제공한다. 이때 푸시와 팝은 힙의 조건을 유지하며 수행된다. 따라서 heapq 모듈을 사용하면 힙 정렬을 아래 코드와 같이 매우 간결하게 구현할 수 있다.
import heapq
from typing import MutableSequence
def heap_sort(a: MutableSequence) -> None:
heap = []
for i in a:
heapq.heappush(heap, i)
for i in range(len(a)):
a[i] = heapq.heappop(heap)heapq.heappush(heap, i): 항상 최소 힙 구조를 유지하면서 원소를 추가heapq.heappop(heap): 힙에서 항상 작은 값을 꺼내는 연산. 원소를 하나씩 꺼낼 때마다 heap이 다시 최소 힙을 유지하기 위해 heapify 연산을 수행한다.
4. 시간 복잡도 및 안정성
| 경우 | 시간 복잡도 |
|---|---|
| 평균 | O(n log n) |
| 최선 | O(n log n) |
| 최악 | O(n log n) |
- 힙 정렬은 항상
O(n log n)의 성능을 보장한다. - 불안정 정렬이므로 동일한 값의 순서가 변경될 수 있다.
- 퀵 정렬보다 느릴 수 있지만, 최악의 경우에도
O(n log n)을 유지한다는 장점이 있다.
💡그럼 시간 복잡도는 왜 O(log n)일까?
트리의 높이를 생각해 보면 쉽게 이해할 수 있다.
- 완전 이진 트리에서 높이(Depth)는
log n - 각 heapify 호출에서 최대
log n번 재귀 호출 발생 - 따라서 한 번 heapify를 수행하는 데 걸리는 시간은
O(log n) - 그리고 힙 정렬 전체 과정에서 heapify를
n번 수행하니까 시간복잡도가O(n log n)이 되는 것이다.
힙 정렬 vs. 퀵 정렬
| 정렬 알고리즘 | 평균 시간 복잡도 | 최악 시간 복잡도 | 안정성 | 추가 메모리 |
|---|---|---|---|---|
| 힙 정렬 | O(n log n) | O(n log n) | ❌ (불안정) | ✅ (제자리 정렬) |
| 퀵 정렬 | O(n log n) | O(n^2) | ❌ (불안정) | ✅ (제자리 정렬) |
✔ 퀵 정렬은 평균적으로 더 빠르지만, 최악의 경우 O(n^2)로 느려질 수 있다.
✔ 힙 정렬은 항상 O(n log n)의 성능을 유지하지만, 캐시 효율성이 낮아 실제 실행 속도는 퀵 정렬보다 느릴 수 있다.
마무리
- 힙 정렬은 이진 힙 구조를 활용하여
O(n log n)성능을 보장하는 정렬 알고리즘이다. - 불안정 정렬이며 추가적인 메모리를 사용하지 않는 제자리 정렬 방식이므로 특정 환경에서 유용하다.
- 퀵 정렬이 최악의 경우
O(n^2)으로 성능이 저하될 수 있는 반면, 힙 정렬은 항상O(n log n)을 유지한다.
