python - Python heapq

 

 

Python heapq

 

 

소개

heapq는 Python에서 힙(Heap) 자료구조를 구현한 라이브러리다. 힙은 완전 이진 트리의 일종으로, 각 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 최소 힙(Min Heap)과 반대로 각 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 최대 힙(Max Heap)이 있다. Python의 heapq 라이브러리는 최소 힙을 구현한다.

 

 

주요 함수

 

heappush(heap, item)

• 기능: item을 heap에 삽입한다.
• 사용 방법: heapq.heappush(heap, item)
• 결과: heap에 item이 삽입되며, 힙 속성이 유지된다.

 

heappop(heap)

• 기능: heap에서 가장 작은 원소를 제거하고 반환한다.
• 사용 방법: heapq.heappop(heap)
• 결과: 가장 작은 원소가 제거되고 반환된다. 만약 heap이 비어 있으면, IndexError가 발생한다.

 

heapify(iterable)

• 기능: iterable을 힙으로 변환한다.
• 사용 방법: heapq.heapify(iterable)
• 결과: iterable이 힙 속성을 가지도록 재정렬된다.

 

예제

import heapq data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]

heap = []



# 데이터를 힙에 삽입

for number in data:

     heapq.heappush(heap, number)



# 힙에서 작은 원소를 제거하고 출력

while heap:

     print(heapq.heappop(heap), end=' ')

 

이 예제에서는 data 리스트의 원소를 heap에 삽입한 후, 힙에서 가장 작은 원소를 차례대로 제거하고 출력한다.

 

 

요약

heapq는 Python에서 최소 힙을 구현한 라이브러리로, 힙에 원소를 삽입하는 heappush, 힙에서 가장 작은 원소를 제거하고 반환하는 heappop, 주어진 리스트를 힙으로 변환하는 heapify 등의 주요 함수를 제공한다. 이를 통해 우선순위 큐 등의 자료구조를 구현할 수 있다.