개념
완전 이진 트리 기반의 힙(Heap) 자료구조를 이용한 정렬
최대 힙을 구성한 후, 최댓값을 차례대로 추출하여 정렬
시간복잡도
| 케이스 | 시간복잡도 |
|---|---|
| 최선 | O(n log n) |
| 평균 | O(n log n) |
| 최악 | O(n log n) |
| 공간복잡도 | O(1) |
특징
장점
- 항상 O(n log n): 최악의 경우에도 보장
- 제자리 정렬: 추가 메모리 O(1)
- 힙 자료구조 활용: 우선순위 큐 구현에 유용
단점
- 불안정 정렬: 같은 값의 순서가 바뀔 수 있음
- 캐시 비효율: 퀵 정렬보다 느림
- 복잡한 구현: 이해하기 어려움
힙(Heap) 이란?
최대 힙 (Max Heap)
부모 노드 ≥ 자식 노드
50
/ \
30 40
/ \ /
10 20 35
최소 힙 (Min Heap)
부모 노드 ≤ 자식 노드
10
/ \
20 30
/ \ /
40 50 35
배열로 표현
# 인덱스 0부터 시작
arr = [50, 30, 40, 10, 20, 35]
# 부모-자식 관계
parent(i) = (i - 1) // 2
left_child(i) = 2 * i + 1
right_child(i) = 2 * i + 2구현 방법
기본 구현
def heap_sort(arr):
n = len(arr)
# 1. 최대 힙 구성 (Build Max Heap)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 2. 하나씩 추출하며 정렬
for i in range(n - 1, 0, -1):
# 루트(최댓값)를 끝으로 이동
arr[0], arr[i] = arr[i], arr[0]
# 힙 속성 복구
heapify(arr, i, 0)
return arr
def heapify(arr, n, i):
"""부분 트리를 힙으로 만들기"""
largest = i
left = 2 * i + 1
right = 2 * i + 2
# 왼쪽 자식이 더 크면
if left < n and arr[left] > arr[largest]:
largest = left
# 오른쪽 자식이 더 크면
if right < n and arr[right] > arr[largest]:
largest = right
# 부모가 최댓값이 아니면 교환하고 재귀
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
# 테스트
print(heap_sort([12, 11, 13, 5, 6, 7]))
# [5, 6, 7, 11, 12, 13]반복문 버전 (재귀 없음)
def heap_sort_iterative(arr):
n = len(arr)
# 1. 최대 힙 구성
for i in range(n // 2 - 1, -1, -1):
heapify_iterative(arr, n, i)
# 2. 정렬
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify_iterative(arr, i, 0)
return arr
def heapify_iterative(arr, n, i):
"""반복문으로 heapify"""
while True:
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest == i:
break
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
# 테스트
print(heap_sort_iterative([12, 11, 13, 5, 6, 7]))
# [5, 6, 7, 11, 12, 13]Python heapq 모듈 활용
import heapq
def heap_sort_heapq(arr):
"""Python heapq 사용 (최소 힙)"""
# 최소 힙으로 변환
heapq.heapify(arr)
# 작은 값부터 추출
result = []
while arr:
result.append(heapq.heappop(arr))
return result
# 테스트
print(heap_sort_heapq([12, 11, 13, 5, 6, 7]))
# [5, 6, 7, 11, 12, 13]
# 주의: heapq는 최소 힙동작 과정
초기: [4, 10, 3, 5, 1]
1단계: 최대 힙 구성
[10, 5, 3, 4, 1]
10
/ \
5 3
/ \
4 1
2단계: 최댓값(10)을 끝으로
[1, 5, 3, 4 | 10] ← 10 확정
3단계: 힙 복구 후 최댓값(5)을 끝으로
[4, 1, 3 | 5, 10] ← 5 확정
4단계: 힙 복구 후 최댓값(4)을 끝으로
[3, 1 | 4, 5, 10] ← 4 확정
5단계: 힙 복구 후 최댓값(3)을 끝으로
[1 | 3, 4, 5, 10] ← 3 확정
완료: [1, 3, 4, 5, 10]
템플릿
def heap_sort_template(arr):
n = len(arr)
# Phase 1: Build Max Heap
# 마지막 부모 노드부터 루트까지
for i in range(n // 2 - 1, -1, -1):
heapify_template(arr, n, i)
# Phase 2: Extract Max
for i in range(n - 1, 0, -1):
# 루트(최댓값)를 끝으로 이동
arr[0], arr[i] = arr[i], arr[0]
# 힙 크기를 줄이고 복구
heapify_template(arr, i, 0)
return arr
def heapify_template(arr, heap_size, root_idx):
"""힙 속성 유지"""
largest = root_idx
left = 2 * root_idx + 1
right = 2 * root_idx + 2
# 자식 중 더 큰 값 찾기
if left < heap_size and arr[left] > arr[largest]:
largest = left
if right < heap_size and arr[right] > arr[largest]:
largest = right
# 부모와 교환 후 재귀
if largest != root_idx:
arr[root_idx], arr[largest] = arr[largest], arr[root_idx]
heapify_template(arr, heap_size, largest)핵심 요약
| 개념 | 설명 |
|---|---|
| 원리 | 최대 힙에서 최댓값을 차례로 추출 |
| 시간복잡도 | O(n log n) - 항상 보장 |
| 공간복잡도 | O(1) |
| 안정성 | 불안정 정렬 |
| 특징 | 제자리 정렬 + O(n log n) 보장 |
다른 정렬과 비교
| 정렬 | 시간복잡도 (평균) | 최악 | 공간복잡도 | 안정성 | 특징 |
|---|---|---|---|---|---|
| 힙 정렬 | O(n log n) | O(n log n) | O(1) | 불안정 | 메모리 효율 |
| 병합 정렬 | O(n log n) | O(n log n) | O(n) | 안정 | 최악 보장 |
| 퀵 정렬 | O(n log n) | O(n²) | O(log n) | 불안정 | 가장 빠름 |
주의사항
1. 인덱스 계산
# 0-based 인덱스
parent(i) = (i - 1) // 2
left(i) = 2 * i + 1
right(i) = 2 * i + 2
# 1-based 인덱스 (책에서 많이 사용)
parent(i) = i // 2
left(i) = 2 * i
right(i) = 2 * i + 12. 불안정 정렬
# 같은 값의 순서가 바뀔 수 있음
arr = [(5, 'a'), (3, 'b'), (5, 'c'), (2, 'd')]
# 정렬 후: (5, 'c')가 (5, 'a')보다 앞에 올 수 있음3. 캐시 효율
# 힙은 트리 구조라 캐시 미스 발생
# 퀵 정렬이 실제로는 더 빠름
# 하지만 O(1) 메모리 + 최악 O(n log n) 보장자주 나오는 문제 유형
1. K번째 큰 수 찾기
문제: 배열에서 K번째로 큰 수 찾기
import heapq
def find_kth_largest(nums, k):
"""최소 힙 이용 (크기 k 유지)"""
heap = []
for num in nums:
heapq.heappush(heap, num)
# 힙 크기가 k를 초과하면 최솟값 제거
if len(heap) > k:
heapq.heappop(heap)
# 힙의 루트가 K번째 큰 수
return heap[0]
# 테스트
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2)) # 5
# 시간복잡도: O(n log k)
# 공간복잡도: O(k)핵심: 크기 k인 최소 힙 유지
2. 배열의 중앙값 (Median) 찾기
문제: 스트림에서 중앙값을 계속 구하기
import heapq
class MedianFinder:
def __init__(self):
# 작은 절반: 최대 힙 (음수로 저장)
self.small = []
# 큰 절반: 최소 힙
self.large = []
def add_num(self, num):
# 작은 쪽에 추가 (최대 힙)
heapq.heappush(self.small, -num)
# 균형 조정: 작은 쪽 최댓값을 큰 쪽으로
if self.small and self.large and (-self.small[0] > self.large[0]):
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
# 크기 균형: 차이가 2 이상이면 조정
if len(self.small) > len(self.large) + 1:
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.large) > len(self.small):
val = heapq.heappop(self.large)
heapq.heappush(self.small, -val)
def find_median(self):
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2
# 테스트
mf = MedianFinder()
mf.add_num(1)
mf.add_num(2)
print(mf.find_median()) # 1.5
mf.add_num(3)
print(mf.find_median()) # 2
# 시간복잡도: add O(log n), find O(1)핵심: 두 개의 힙으로 중앙값 유지
3. Top K Frequent Elements
문제: 가장 빈번한 K개의 요소 찾기
import heapq
from collections import Counter
def top_k_frequent_heap(nums, k):
"""최소 힙 이용"""
count = Counter(nums)
# 크기 k인 최소 힙 유지
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for freq, num in heap]
# 테스트
print(top_k_frequent_heap([1, 1, 1, 2, 2, 3], 2))
# [2, 1]
# 시간복잡도: O(n log k)핵심: 빈도수를 키로 힙에 저장
4. 배열을 거의 정렬하기 (K-Sorted)
문제: 각 요소가 최대 K칸 떨어진 위치에 있는 배열 정렬
import heapq
def sort_k_sorted_array(arr, k):
"""거의 정렬된 배열 정렬"""
result = []
heap = []
# 처음 k+1개 요소를 힙에 추가
for i in range(min(k + 1, len(arr))):
heapq.heappush(heap, arr[i])
# 나머지 요소 처리
for i in range(k + 1, len(arr)):
result.append(heapq.heappop(heap))
heapq.heappush(heap, arr[i])
# 힙에 남은 요소 추가
while heap:
result.append(heapq.heappop(heap))
return result
# 테스트
print(sort_k_sorted_array([3, 2, 1, 5, 4, 7, 6, 5], 3))
# [1, 2, 3, 4, 5, 5, 6, 7]
# 시간복잡도: O(n log k)핵심: 크기 k+1인 힙만 유지
5. 가장 가까운 K개의 점
문제: 원점에서 가장 가까운 K개의 점 찾기
import heapq
def k_closest_points(points, k):
"""원점에서 가장 가까운 K개의 점"""
# 최대 힙 (거리의 음수 저장)
heap = []
for x, y in points:
distance = -(x*x + y*y) # 음수로 최대 힙
heapq.heappush(heap, (distance, [x, y]))
if len(heap) > k:
heapq.heappop(heap)
return [point for dist, point in heap]
# 테스트
points = [[1, 3], [-2, 2], [5, 8], [0, 1]]
print(k_closest_points(points, 2))
# [[0, 1], [-2, 2]] 또는 [[-2, 2], [0, 1]]
# 시간복잡도: O(n log k)핵심: 거리 기준으로 최대 힙 유지
추천 연습 문제
기초
중급
- LeetCode 215 - Kth Largest Element
- LeetCode 295 - Find Median from Data Stream
- LeetCode 347 - Top K Frequent Elements
고급
힙 정렬 vs 우선순위 큐
힙 정렬
# 전체 배열을 한 번에 정렬
arr = [5, 3, 8, 1, 2]
heap_sort(arr) # [1, 2, 3, 5, 8]우선순위 큐
import heapq
# 동적으로 요소 추가/제거
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
min_val = heapq.heappop(heap) # 3
# 스트림 데이터 처리에 유용언제 사용할까?
사용 가능
- 메모리 제한: O(1) 공간복잡도
- 최악 보장: O(n log n) 항상 보장
- 우선순위 큐: Top K, 중앙값 등
- K개 요소 찾기: O(n log k)
사용 불가
- 안정 정렬 필요: 병합 정렬 사용
- 평균 성능 중요: 퀵 정렬이 더 빠름
- 작은 데이터: 삽입 정렬이 더 나음
결론: 메모리 효율 + 최악 보장이 필요하거나, 우선순위 큐 문제에 최적!