PHpullh
학습 라이브러리/Python/heapq 힙 큐

PYTHON · 컬렉션

heapq 힙 큐

heapq로 우선순위 큐를 구현합니다. 최솟값/최댓값을 O(log n)에 추출합니다.

컬렉션중급heapq힙우선순위 큐priority queue

핵심 설명

heapq로 우선순위 큐를 구현합니다. 최솟값/최댓값을 O(log n)에 추출합니다.

Python code

import heapq

# 기본 힙 연산
data = [5, 3, 8, 1, 9, 2]
heapq.heapify(data)  # 리스트를 힙으로 변환 O(n)
print(data)  # [1, 3, 2, 5, 9, 8]

# 삽입과 추출
heapq.heappush(data, 0)
print(heapq.heappop(data))   # 0 (최솟값)
print(heapq.heappop(data))   # 1

# nlargest / nsmallest
scores = [85, 92, 78, 95, 88, 76, 91]
print(heapq.nlargest(3, scores))   # [95, 92, 91]
print(heapq.nsmallest(3, scores))  # [76, 78, 85]

# 우선순위 큐 구현
class PriorityQueue:
    def __init__(self):
        self._heap = []
        self._counter = 0

    def push(self, priority: int, item):
        heapq.heappush(self._heap, (priority, self._counter, item))
        self._counter += 1

    def pop(self):
        return heapq.heappop(self._heap)[2]

pq = PriorityQueue()
pq.push(2, "낮은 우선순위")
pq.push(0, "높은 우선순위")
pq.push(1, "중간 우선순위")
print(pq.pop())  # 높은 우선순위

학습 팁

heapq는 최소 힙만 지원합니다. 최대 힙이 필요하면 값에 -1을 곱하세요.

주의할 점

heapq에서 튜플 비교 시 첫 번째 요소가 같으면 두 번째 요소를 비교합니다. 비교 불가능한 객체면 에러가 발생하므로 카운터를 추가하세요.

자주 묻는 질문

heapq 힙 큐란 무엇인가요?

heapq 로 우선순위 큐를 구현합니다. 최솟값/최댓값을 O(log n)에 추출합니다.

heapq 힙 큐 학습 시 주의할 점은 무엇인가요?

heapq 에서 튜플 비교 시 첫 번째 요소가 같으면 두 번째 요소를 비교합니다. 비교 불가능한 객체면 에러가 발생하므로 카운터를 추가하세요.