heapq 모듈은 파이썬의 내장 모듈이다.
힙은 자료구조이며 heapq 모듈은 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와주는 역할을 한다. 리스트를 힙으로 바꾸지 않아도 리스트에 뭔가를 더하거나 뺄때 heapq의 함수를 사용하면서 그 리스트를 인자로 넣으면 힙큐가 된다!
.heappush(list, value) : insert나 push 종류다. 좋은점은 그냥 넣으면 알아서 힙의 형태로 정렬된다는 것이다. 단 부모와 자식은 정렬되어도 자식과 자식간에는 대소관계가 없으므로 주의!
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)
[1, 3, 7, 4]heapq.heappop(list) : 리스트를 인자로 주면 알아서 가장 작은 값(deque의 popleft처럼 가장 앞에 있다)을 삭제한 후에 다시 힙정렬되어 리턴한다.
print(heapq.heappop(heap))
print(heap)
1
[3, 4, 7]안에 있는 힙은 계속 바뀌기 때문에 항상 최소값을 뺄 수 있다는 장점!
heapq.heapify(heap2) : 이미 원소가 들어있는 리스트를 힙구조로 만들어준다!
heapify함수에 리스트를 인자로 넘기면 리스트 내부의 원소들이 방금 하나씩 heappush한 것처럼 힙 구조에 맞게 재배치되며 최소값이 0번째 인덱스로 이동된다.
heap2 = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap2)
print(heap2)
[1, 3, 5, 4, 8, 7]즉 종합하면, pop을 하나씩 하면 무조건 최소값이 빠지게 된다는 거다!
왜냐하면 트리니까! 정말 좋은 모듈이다.
최대힙 만들기
heapq 모듈은 최소 힙(min heap) 기능만 동작하기 때문에 최대 힙(max heap)으로 활용하려면 약간의 요령이 필요하다.
힙에다가 튜플(tuple)를 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용한 것인데 간단하게 힙에 있는 모든 값의 -음수 데이터를 원래의 데이터와 튜플로 묶어서 push해준다.
import heapq
nums = [4, 1, 7, 3, 8, 5]
heap = []
for num in nums:
heapq.heappush(heap, (-num, num)) # (우선 순위, 값)
while heap:
print(heapq.heappop(heap)[1]) # 가져올땐 간단히 인덱싱[1]예제 : 미니멀한 함수
heapq.nsmallest(k, list) : k번째까지 빼주세요를 간단하게 줄인 함수
k번째 작은 숫자를 리턴해달라는 문제가 나오면 그냥 얘를 써주면 된다.
리스트를 먼저 힙큐파이 해줘야됨 주의!
heapq.nlargest(k, list) : 스몰리스트 쌍둥이인데 k번째까지의 큰 수를 리턴해주는 함수다! 날먹이다. 내장함수를 잘 쓰자!
import heapq
data = [
(12.23, "강00"),
(12.31, "김00"),
(11.67, "차00"),
(12.02, "박00"),
(11.57, "차00"),
(12.04, "고00"),
(11.92, "한00"),
]
print(heapq.nsmallest(3, data)) # 금은동 찾기 예제문제