[Python] heapq 모듈

💡heapq 모듈💡

heapq 모듈은 우선순위 큐 알고리즘의 구현을 제공한다. 힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진트리이다.

💡heapq 모듈 함수💡

(1) heappush(heap, item) 함수

item값을 heap에 추가한다.

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

>>> print(heap)
[10, 50, 20]

(2) heappop(heap) 함수

heap에서 가장 작은 항복을 제거한 후 반환한다. 이 때, heap이 비어있으면 IndexError가 발생한다.

import heapq

heap = [10, 50, 20]
heapq.heappop(heap)

>>> print(heap)
[20, 50]

(3) heappushpop(heap, item) 함수

heap에 tiem을 추가하고, ehap에서 가장 작은 항복을 제거하고 반환한다. heappush한 다음 heappop을 각각 수행하는 것보다 효율적이다.

import heapq

heap = [10, 50, 20]
heapq.heappushpop(heap, 90)

>>> print(heap)
[20, 50, 90]

(4) heapify(x) 함수

list x를 heap으로 변환합니다.

import heapq

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)

>>> print(heap)
[1, 3, 5, 4, 8, 7]

(5) nsmallest(n, heap, key = None) 함수

heap에 의해 정의된 데이터 집합에서 n개의 가장 큰 요소로 구성된 list를 반환한다.

import heapq

heap = [1, 3, 5, 4, 8, 7]

>>> print(heapq.nsmallest(3, heap))
[1, 3, 4]

(6) nlargest(n, heap, key = None) 함수

heap에 의해 정의된 데이터 집합에서 n개의 가장 작은 요소로 구성된 list를 반환한다.

import heapq

heap = [1, 3, 5, 4, 8, 7]

>>> print(heapq.nlargest(3, heap))
[8, 7, 5]