[Python] heapq 모듈

이번 포스팅에서는 파이썬 내장 모듈 중 하나인 heapq에 대하여 공부를 해보고자 한다.

 

---

heapq란

heapq 모듈은 Python 표준 라이브러리의 일부로서, 힙(Heap) 자료 구조를 구현하는 데 사용된다.|
힙은 우선순위 큐(Priority Queue)를 구현하는 데 사용되는 자료 구조로, 가장 작은 (또는 가장 큰) 요소에 빠르게 접근할 수 있는 효율적인 방법을 제공한다.

 

heapq 모듈은 주로 리스트를 사용하여 힙을 구현한다.
리스트는 이진 트리로써 힙의 구조를 나타내며, 다음과 같은 함수들을 제공하여 힙의 조작과 관련된 작업을 수행할 수 있다.

• heapify(iterable)
  주어진 iterable을 힙으로 변환한다.
  입력으로 주어진 리스트나 반복 가능한 객체를 힙으로 변환하여 해당 리스트를 변경한다.
• heappush(heap, item)
  힙에 요소를 추가한다.
  요소는 힙의 규칙에 따라 적절한 위치에 삽입된다.
  
  
• heappop(heap)
  힙에서 가장 작은 요소를 제거하고 반환한다.
  
  
• heapreplace(heap, item)
  힙의 가장 작은 요소를 제거하고 주어진 요소를 삽입한다.
  이 함수는 heappop( )과 heappush( )를 조합한 것과 같은 역할을 수행하지만, heappop( )과 달리 힙이 비어 있을 때에도 작동한다.
  
  
• heappushpop(heap, item)
  heapreplace( )와 유사하지만, item을 힙에 직접 추가하지 않고, 현재 힙에 있는 가장 작은 요소와 item을 비교한 후 결과를 반환한다.
  
  
• heapreplace( ), heappushpop( ) 함수는 heappop( )보다 효율적인 방법이다.
  이들 함수는 힙의 상태를 변경하지 않기 때문에, 힙에 있는 요소들 중 작은 값들을 반복적으로 추가하거나 제거하는 작업에 유용하다.

 

---

예시

다음은 heapq 모듈의 몇 가지 사용 예시이다.

 

힙 생성 및 조작

import heapq

# 리스트를 힙으로 변환
lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
heapq.heapify(lst)
print(lst)  # [1, 1, 2, 3, 3, 9, 4, 6, 5, 5]

# 힙에 요소 추가
heapq.heappush(lst, 0)
print(lst)  # [0, 1, 1, 3, 3, 2, 2, 6, 5, 5, 9, 4]

# 힙에서 가장 작은 요소 제거 및 반환
min_element = heapq.heappop(lst)
print(min_element)  # 0
print(lst)  # [1, 1, 2, 3, 3, 2, 4, 6, 5, 5, 9]

# 힙의 가장 작은 요소 제거 후 새로운 요소 추가
min_element = heapq.heapreplace(lst, 7)
print(min_element)  # 1
print(lst)  # [1, 2, 2, 3, 3, 7, 4, 6, 5, 5, 9]

 

우선순위 큐로 활용

import heapq

# 우선순위 큐 생성
pq = []
heapq.heappush(pq, (3, 'Task 1'))
heapq.heappush(pq, (1, 'Task 2'))
heapq.heappush(pq, (2, 'Task 3'))

# 우선순위에 따라 작업 처리
while pq:
    priority, task = heapq.heappop(pq)
    print(f"Processing task '{task}' with priority {priority}")
    
# 출력
Processing task 'Task 2' with priority 1
Processing task 'Task 3' with priority 2
Processing task 'Task 1' with priority 3

 

최대 힙 구현

import heapq

# 음수 값을 활용하여 최대 힙 구현
max_heap = []
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
for num in nums:
    heapq.heappush(max_heap, -num)

# 최대 힙에서 요소 제거
while max_heap:
    max_element = -heapq.heappop(max_heap)
    print(max_element)
    
# 출력
9
6
5
5
4
3
3
2
1
1

 

 

 

---