[python] heap

heapq

• 파이썬의 표준 라이브러리에 포함된 힙 큐 알고리즘 모듈
• 이진 트리 기반의 최소 힙(min heap) 자료구조 제공
• 리스트를 직접 힙으로 조작할 수 있는 함수들을 포함

사용방법

• import heapq 하여 사용 가능

주요 메서드

• heappush()
  • 요소를 힙에 추가하는 함수

import heapq
heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)

• heappop()
  • 힙에서 가장 작은 요소를 제거하고 반환

smallest = heapq.heappop(heap)

• heapify()
  • 기존 리스트를 힙 구조로 변환

numbers = [5, 1, 7, 3]
heapq.heapify(numbers)

활용

• 최대 힙 구현
  • 음수 값을 이용해 최대 힙 구현 가능

max_heap = []
heapq.heappush(max_heap, (-value, value))

추가 유용한 함수들

• nsmallest(): n개의 가장 작은 요소 반환
• nlargest(): n개의 가장 큰 요소 반환
• heappushpop(): 요소 추가 및 최소값 제거를 동시에 수행

성능 특징

• 요소 삽입 및 제거 시 O(log n) 시간 복잡도
• 리스트와 트리의 장점을 결합한 효율적인 자료구조
• 우선순위 큐 구현에 매우 적합

주의사항

• 기본적으로 최소 힙 구조
• 요소 추가/제거 시 자동으로 힙 속성 유지