[파이썬 라이브러리] heapq

 

힙 큐 (heap queue)

 - 힙큐(heap queue) = 우선순위 큐 (priority queue)

 - heapq에서는 요소를 0부터 세서, heap[k]의 left-child는 heap[2*k+1], right-child는 heap[2*k+2]이다.

     >>> 1부터 만들면 편하지만, 파이썬은 0부터

 - heapq의 heap은 기본적으로 최소힙(min heap)

 - 기본적으로 list를 사용함

 

 

 

heaq 함수

함수	파라미터	설명
heappush	heap, item	item을 heap으로 푸시
heappop	heap	pop 하고 반환. 빈 힙이면 IndexError
heappushpop	heap, item	item을 push하고 가장 작은 항목을 pop (함수 두개 보다 효율적)
heapify	x	리스트 x를 힙(min heap)으로 변환. return 값 없음
heapreplace	heap, item	pop하고 push. 빈힙이면 IndexError
merge	*iterables, key=None, reverse=False	여러 heap을 하나의 heap으로 merge. iterator 반환   - key : 입력 요소에서 비교 키를 추출할때 사용되는 키 함수   - reverse : 비교가 반대로 이뤄짐
nlargest	n, iterable, key=None	n개의 가장 큰 요소를 리스트로 반환   - key : 예시로 key=str.lower 등..
nsmallest	n, iterable, key=None	n개의 가장 작은 요소를 리스트로 반환

 

 

 

 

heapify, heappush, heappop, heappushpop, heapreplace

import heapq

myHeap = [5, 4, 6, 2, 8, 7, 1, 3, 9]

heapq.heapify(myHeap)
print(type(myHeap))
print(myHeap, end='\n\n')

print(heapq.heappop(myHeap))
print(myHeap)

heapq.heappush(myHeap, 10)
print(myHeap, end='\n\n')

print(heapq.heappushpop(myHeap, 11))
print(myHeap, end='\n\n')

print(heapq.heapreplace(myHeap, 12))
print(myHeap, end='\n\n')

 

 - heapify는 반환값 X

 - heappushpop, heapreplace 는 push와 pop을 따로 수행하는 것 보다 효율적

 

 

 

merge

import heapq

myHeap1 = [9, 7, 1, 3, 5]
myHeap2 = [10, 8, 2, 4, 6]

heapq.heapify(myHeap1)
heapq.heapify(myHeap2)
print(myHeap1)
print(myHeap2)
print()

myHeap = heapq.merge(myHeap1, myHeap2)

print(type(myHeap))
print(myHeap)
print(myHeap1)
print(myHeap2)
print()

myHeap = list(myHeap)
print(type(myHeap))
print(myHeap)

 

 - merge는 heap에서 heap으로

 - generator를 반환하므로 list로 바꿔줘야 함

 

 

 

nlargest, nsmallest

import heapq

myHeap = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

print(heapq.nlargest(3, myHeap))
print(heapq.nsmallest(3, myHeap))
print(myHeap)

 

 - 원래 heap은 건들지 않음. (pop 아님)

 - nlargest는 내림차순으로, nsmallest은 오름차순으로 정렬됨

 

 

 

최대 힙 (max heap)으로의 응용

import heapq

myList = [1, 2, 3, 4, 5, 6, 7, 8, 9]
myHeap = []

# push
for n in myList:
    heapq.heappush(myHeap, (-n, n))
print(myHeap)


# pop
print(heapq.heappop(myHeap)[1])

 

 - tuple을 이용해서 거꾸로 정렬.

 - 그냥 음수로 넣고 뺄때 부호 바꿔서 빼줘도 될듯

 

 

 

참조
 - 파이썬 공식 문서