힙 큐(Heap Queue)란 무엇인가?
힙(Heap) 자료구조는 우선순위 큐(Priority Queue)를 효율적으로 구현하기 위해 널리 사용됩니다. 파이썬에서는 별도의 설치 없이 기본 제공되는 heapq 모듈을 통해 힙 기능을 바로 활용할 수 있습니다.
heapq 모듈은 최소 힙(Min-Heap) 방식으로 동작합니다. 즉, 값이 작을수록 더 높은 우선순위를 갖습니다. 예를 들어 숫자 1이 최우선순위가 되며, 새로운 요소가 삽입되거나 삭제될 때마다 힙 구조가 자동으로 재정렬되어 항상 최솟값이 루트(맨 앞)에 위치하게 됩니다.
heapq 모듈 임포트하기
heapq는 파이썬 표준 라이브러리에 포함되어 있으므로, 아래 한 줄만 추가하면 바로 사용할 수 있습니다.
import heapq
heapq의 주요 메서드 살펴보기
1. heapq.heapify(iterable)
리스트와 같은 반복 가능한(iterable) 데이터를 힙 구조로 변환합니다. 변환은 선형 시간(O(n)) 안에 수행되며, 기존 리스트를 그대로 힙 속성을 만족하도록 재배열합니다.
2. heapq.heappush(heap, element)
힙에 새로운 요소를 삽입합니다. 요소가 추가된 후 전체 힙 구조가 자동으로 재정렬되어 힙 속성이 유지됩니다.
3. heapq.heappop(heap)
힙의 루트에 있는 요소(최솟값)를 반환하고 삭제합니다. 삭제 후에는 나머지 요소들로 힙 구조가 다시 구성됩니다.
4. heapq.heappushpop(heap, element)
삽입과 팝 연산을 하나의 문장으로 처리합니다. 먼저 새 요소를 힙에 추가한 뒤, 루트의 최솟값을 꺼내 반환합니다.
5. heapq.heapreplace(heap, element)
heappushpop과 마찬가지로 삽입과 팝을 한 번에 수행하지만, 처리 순서가 반대입니다. 먼저 루트의 요소를 제거한 후 새로운 요소를 삽입합니다.
6. heapq.nlargest(n, iterable, key=None)
데이터 집합에서 가장 큰 n개의 요소를 내림차순 리스트 형태로 반환합니다.
7. heapq.nsmallest(n, iterable, key=None)
데이터 집합에서 가장 작은 n개의 요소를 오름차순 리스트 형태로 반환합니다.
예제 코드
아래 예제는 힙 생성부터 요소 삽입, 삭제, 최댓값 추출까지 heapq의 대표적인 기능을 보여줍니다.
import heapq
my_list = [58, 41, 12, 17, 89, 65, 23, 20, 10, 16, 17, 19]
# 리스트를 힙 구조로 변환
heapq.heapify(my_list)
print(my_list)
# 힙에 새로운 요소 삽입
heapq.heappush(my_list, 7)
print(my_list)
# 힙에서 최솟값 꺼내기
print('Popped Element: ' + str(heapq.heappop(my_list)))
print(my_list)
# 가장 큰 4개의 요소 추출
new_iter = list()
new_iter = heapq.nlargest(4, my_list)
print(new_iter)
실행 결과
[10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65] [7, 16, 10, 17, 17, 12, 23, 20, 41, 89, 58, 65, 19] Popped Element: 7 [10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65] [89, 65, 58, 41]
마무리
실행 결과를 보면 heapify를 거친 리스트의 첫 번째 위치에 항상 최솟값이 오고, heappush로 삽입한 7이 곧바로 루트로 올라온 뒤 heappop으로 가장 먼저 꺼내지는 것을 확인할 수 있습니다. 또한 nlargest를 사용하면 전체를 정렬하지 않고도 상위 n개의 값을 빠르게 얻을 수 있습니다.
이처럼 heapq 모듈은 작업 스케줄링, 다익스트라(Dijkstra) 최단 경로 알고리즘, 실시간 데이터 스트림에서 상위 k개 값 추적 등 우선순위 기반 처리가 필요한 다양한 상황에서 유용하게 활용됩니다.