heapq

 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 한 자료구조인 힙을 구현한 모듈. 우선순위 큐를 구현하는데 사용될 수 있다. 다음과 같은 구조의 리스트 형태로 존재한다.

heap[k] <= heap[2*k+1]
heap[k] <= heap[2*k+2]

 이때 첫 원소인 heap[0]는 가장 작은 값이다. 기본적으로 최소힙을 구현하고 있으며 넣으려는 값에 -를 붙여삽입한뒤 꺼낼때 다시 해당 부호를 없애는 방식을 통해 최대힙으로도 사용할 수 있다.

제공 함수

heappush(heap, item)

힙 불변성을 유지하면서 item을 heap에 추가.

import heapq
lst =[]
heapq.heappush(lst,5)
heapq.heappush(lst,4)
heapq.heappush(lst,3)
heapq.heappush(lst,2)
heapq.heappush(lst,1)
print(lst)
#[1, 2, 4, 5, 3]

## heappop(heap)
힙 불변성을 유지하면서 가장 작은 값을 heap에서 pop
>
```python
print(heapq.heappop(lst))
#1
print(lst)
#[2, 3, 4, 5]

heappushpop(heap, item)

힙 불변성을 유지하면서 heap에 item을 넣고 가장 작은 값을 pop. heappush, heappop을 연달아 실행하는 것 보다 효율적인 동작.

print(heapq.heappushpop(lst,1)
#1
print(lst)
#[2, 3, 4, 5]

heapify(x)

리스트 x를 힙 형태로 변환. 길이만큼의 선형시간 소요.

lst = [5,4,3,2]
heapq.heapify(lst)
print(lst)
#[2, 4, 3, 5]

heapreplace(heap, item)

heap에 가장 작은 값을 pop 하고, 새로운 item을 push. 힙의 크기 변동이 없음. heappop, heappush 보다 효율적인 동작. 이 동작에서는 pop된 값이 item 보다 클 수 있음. 경우에 따라 heappushpop 과 선택해서 사용.

print(heap.heapreplace(lst,1)
#2
print(lst)
#[1, 4, 3, 5]

heapq.merge(*iterables, key=None, reverse=False)

여러 iterable들을 정렬해서 연결. sorted(itertools.chain(*iterable))과 유사하지만, 모든 iterable을 메모리에 올리지 않고 제너레이터를 생성. 단 이때의 입력되는 iterable은 이미 정렬된 것으로 간주됨.

lst1 = [1,3,5,7]
lst2 = [2,4,6,8]
print(heapq.merge(lst1,lst2))
#<generator object merge at 0x00000239525CE8F0>
for i in heapq.merge(lst1,lst2):
	print(i)
# 1
# 2
# 3
# 4
# 5
# 6
# 7
# 8

heapq.nlargest(n, iterable, key=None)

key로 주어진 함수를 기준으로 iterable에서 큰 순으로 n개를 반환

print(heapq.nlargest(3,lst))
#[5, 4, 3]
print(lst)
#[1, 4, 3, 5]

heapq.nsamllest(n, iterable, key=None)

key로 주어진 함수를 기준으로 iterable에서 작은 순으로 n개를 반환
largest, smallest 두 함수는 n이 작을 때 효율적임. n==1 이면 min,max를 사용하고, n이 크면 그냥 sorted(iterable)을 통해 구하는게 더 효율적. 해당 함수들을 반복해서 사용한다면 iterable을 힙으로 변경하는 것이 좋음.

print(heapq.nsmallest(3,lst))
#[1, 3, 4]
print(lst)
#[1, 4, 3, 5]