파이썬 heapq 모듈 완전 정복 📊

파이썬 heapq 모듈 완전 정복 📊

heapq는 리스트를 힙 자료구조로 다뤄 효율적인 최소/최댓값 추출 및 정렬이 가능하게 해줍니다. 특히 우선순위 큐 구현에 매우 유용합니다.

1. 최소 힙 생성 및 기본 사용

import heapq

nums = [5, 1, 8, 3, 2]
heapq.heapify(nums)
print(nums)  # 최소 힙 구조로 변경

print(heapq.heappop(nums))  # 1 (최솟값 추출)
print(heapq.heappop(nums))  # 2

2. 힙에 요소 추가

import heapq

heapq.heappush(nums, 0)
print(nums)  # 0이 힙에 삽입, 루트가 0

3. 최댓값 추출을 위한 힙 변형

import heapq

nums2 = [5,1,8,3,2]
max_heap = [-n for n in nums2]
heapq.heapify(max_heap)
print(-heapq.heappop(max_heap))  # 8

4. 상위 n개/하위 n개 값 추출

import heapq

data = [9,1,7,4,6,3,8]
print(heapq.nlargest(3, data))  # [9,8,7]
print(heapq.nsmallest(2, data)) # [1,3]

5. 힙 정렬 구현

import heapq

def heap_sort(iterable):
    h = []
    for v in iterable:
        heapq.heappush(h, v)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heap_sort([4,1,7,3,9]))  # [1,3,4,7,9]

요약

• 리스트에 대해 heapify로 최소 힙 구조 생성
• heappop/heappush로 효율적인 값 추출 및 삽입
• 부호 반전으로 최대 힙처럼 동작하도록 활용 가능
• nlargest/nsmallest로 상위/하위 n개 요소 바로 얻기
• 힙을 이용한 간단한 힙 정렬 함수 구현