[heapq] 최소힙, 최대힙

import heapq

최소값 혹은 최대값을 자주 참조하면서 자료구조 원소들을 변경하는 경우 힙을 사용하는게 유리합니다.

파이썬에서 제공하는 heap 자료구조 입니다. 배열을 heap 구조로 사용할 수 있고, push pop 기능을 제공합니다.

heapq — Heap queue algorithm

 

기본적으로 최소힙 형태로 기능합니다.

파이썬은 튜플도 대소비교가 가능하기 때문에 원소를 (key, value) 튜플로 넣으면 최대힙처럼 사용할수도 있습니다. key에 value의 음수값을 넣는 것이죠.

 

메서드 요약

heapq.heappush(heap, item)

heapq.heappop(heap)

heapq.heappushpop(heap, item) # 푸시하고 팝하기

heapq.heapify(x) # 기존의 리스트를 힙형태로 정렬

heapq.heapreplace(heap, item) # 팝하고 푸시하기

heapq.merge(*iterables, key=None, reverse=False) # 여러 이터러블한 객체들을 입력받아서 결합, 리스트가 아닌 이터레이터를 반환, 입력은 오름차순 정렬되어있어야함.

heapq.nlargest(n, iterable, key=None) # 큰 원소 n개만 뽑아서 리스트 반환

heapq.nsmallest(n, iterable, key=None) # 작은 원소 n개만 뽑아서 리스트 반환