heap

기본 사용법 (최소 힙) 

파이썬은 최소 힙만 가능

import heapq

heap = []

# 원소 추가 (push)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

print(heap)  # [1, 3, 7, 4] ← 내부적으로 힙 구조로 정렬되어 있음

# 최솟값 꺼내기 (pop)
smallest = heapq.heappop(heap)
print(smallest)  # 1
print(heap)      # [3, 4, 7]

 

리스트를 힙으로 한 번에 변환

arr = [5, 3, 8, 1]
heapq.heapify(arr)
print(arr)  # [1, 3, 8, 5]

 

최대힙

파이썬 heapq는 기본이 최소 힙이라, 값에 -를 붙여서 반대로 저장

heap = []
heapq.heappush(heap, -3)
heapq.heappush(heap, -1)
heapq.heappush(heap, -7)

# 가장 큰 값 꺼내기
largest = -heapq.heappop(heap)
print(largest)  # 7

 

성능 위해 push pop 동시 사용

heappushpop(heap, item) # push -> pop

heapreplace(heap, item) # pop -> push

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

# 새 값 넣고 최소값 바로 꺼내기
x = heapq.heappushpop(heap, 2)
print(x)     # 1 (꺼낸 값)
print(heap)  # [2, 3, 5]


import heapq

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

print(heapq.heappushpop(heap, 0))  # 0, 힙 그대로 [1, 3, 5]
print(heap)                        # [1, 3, 5]

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

print(heapq.heapreplace(heap, 0))  # 1, 힙 바뀜 [0, 3, 5]
print(heap)                        # [0, 3, 5]