파이썬(python) 라이브러리 - heapq

---

heapq

---

파이썬에서 힙 (우선순위 큐) 자료구조를 이용할때 사용한다.

C++, 자바는 우선순위 큐 자료구조를 제공하지만

파이썬은 리스트를 우선순위 큐 처럼 다룰 수 있는 함수를 제공한다.

 

최소 힙 (Default)

heap = [] : 리스트
heapq.heappush(heap, 원소) : 힙에 하나 추가 O(logN)
a = heapq.heappop(heap)    : 힙에서 하나 빼서 반환 O(logN)
heap[0] : 힙에서 빼지않고 값 얻기 O(1)


이미 값이 있는 리스트를 힙으로 사용하려면 변환이 필요
heapq.heapify(heap)        : 변환 (리스트 → 힙) O(N)

최대 힙

튜플의 첫 번째 원소가 기준이 되는 것을 이용

heap = [] : 리스트
p = [4,3,2,5]

heapq.heappush(heap, (-p, p)) : 힙에 하나 추가 O(logN)
a = heapq.heappop(heap)[1]    : 힙에서 하나 빼서 반환 O(logN)
heap[0][1]                    : 힙에서 빼지않고 값 얻기 O(1)


이미 값이 있는 리스트를 힙으로 사용하려면 변환이 필요
heapq.heapify_max(heap)        : 변환 (리스트 → 힙) O(N)

그 외 

a = heapq.heappushpop(heap, 원소) : 힙에 하나 추가하고 하나 빼서 반환
(heappush() → heappop() 순서로 호출하는 것 보다 효율적)

a = heapq.heapreplace(heap, 원소) : 힙에서 하나 빼서 반환 후 하나 추가
(heappop() → heappush() 순서로 호출하는 것 보다 효율적)



n개의 가장 큰 요소로 구성된 리스트 반환
a = heapq.nlargest(n, heap, key=None)

n개의 가장 작은 요소로 구성된 리스트 반환
a = heapq.nsmallest(n, heap, key=None)

key=요소 비교에 사용되는 함수
n이 너무크면 sorted가 효율적임