[Python] 파이썬 힙(Heap) 완벽 가이드: 우선순위 큐 구현의 핵심, 초보자도 쉽게 이해하는 방법
파이썬 힙(Heap) 완벽 가이드: 우선순위 큐 구현의 핵심, 초보자도 쉽게 이해하는 방법
파이썬 힙(Heap)은 우선순위 큐(Priority Queue)를 구현하는 데 사용되는 자료구조입니다. 힙은 특정 순서 속성을 만족하는 완전 이진 트리(Complete Binary Tree)이며, 최소값 또는 최대값을 효율적으로 찾고 관리할 수 있도록 도와줍니다. 이 글에서는 파이썬 힙의 기본 개념, heapq 모듈 사용법, 힙 정렬 등을 예제 코드와 함께 자세히 설명합니다.
1. 힙(Heap)이란 무엇인가?
힙은 다음과 같은 속성을 만족하는 완전 이진 트리입니다.
- 최소 힙(Min Heap): 부모 노드의 키(key)가 자식 노드의 키보다 작거나 같은 힙입니다.
- 최대 힙(Max Heap): 부모 노드의 키가 자식 노드의 키보다 크거나 같은 힙입니다.
힙은 주로 우선순위 큐를 구현하는 데 사용되며, 다음과 같은 장점을 가집니다.
- 최소값 또는 최대값을 빠르게 찾을 수 있습니다.
- 삽입 및 삭제 연산이 효율적입니다.
2. heapq 모듈 사용법
파이썬은 heapq 모듈을 통해 힙 자료구조를 제공합니다.
2.1. 힙 생성
빈 리스트를 생성하고 heapq.heapify() 함수를 사용하여 리스트를 힙으로 변환합니다.
import heapq
heap = []
heapq.heapify(heap)
2.2. 요소 추가
heapq.heappush() 함수를 사용하여 힙에 요소를 추가합니다.
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
2.3. 최소값 삭제
heapq.heappop() 함수를 사용하여 힙에서 최소값을 삭제하고 반환합니다.
min_value = heapq.heappop(heap)
print(min_value) # 출력: 1
2.4. 최소값 확인
heap[0]을 사용하여 힙의 최소값을 확인할 수 있습니다.
min_value = heap[0]
print(min_value) # 출력: 3
3. 힙 정렬(Heap Sort)
힙을 사용하여 데이터를 정렬하는 알고리즘입니다.
def heap_sort(arr):
heapq.heapify(arr)
sorted_arr = []
while arr:
sorted_arr.append(heapq.heappop(arr))
return sorted_arr
arr = [4, 1, 7, 3, 8, 5]
sorted_arr = heap_sort(arr)
print(sorted_arr) # 출력: [1, 3, 4, 5, 7, 8]
4. 최대 힙(Max Heap) 구현
파이썬 heapq 모듈은 기본적으로 최소 힙을 제공합니다. 최대 힙을 구현하려면 요소에 음수를 취하여 최소 힙을 사용합니다.
max_heap = []
heapq.heapify(max_heap)
heapq.heappush(max_heap, -4)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -7)
max_value = -heapq.heappop(max_heap)
print(max_value) # 출력: 7
5. 결론
파이썬 힙은 우선순위 큐를 구현하고 데이터를 효율적으로 관리하는 데 유용한 자료구조입니다. heapq 모듈을 사용하여 힙을 생성하고 다양한 연산을 수행할 수 있습니다. 힙 정렬과 최대 힙 구현 방법을 익히고, 필요에 따라 적절한 방법을 선택하여 사용하면 더욱 효율적인 파이썬 코드를 작성할 수 있습니다.