[Python(파이썬)] 힙큐(heapq) 모듈

힙(heap)의 설명은 아래 정리해두었다. 

[자료구조] 힙(heap)

 

 

heapq 모듈  

Python의 heapq 모듈 (= JAVA의 PriorityQueue 클래스)

 

이진 트리(binary tree)기반의 최소 힙(min heap) 자료구조

 

# heapq -> 내장 모듈
import heapq

 

 

• heapq.heappush(Heap, item) - 노드 삽입

# 빈 heap 생성
>>> heap = []
# 8 삽입
>>> heapq.heappush(heap, 8)
>>> heap
[8]
>>> heapq.heappush(heap, 3)
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 7)
>>> heapq.heappush(heap, 6)
>>> heap
[1, 6, 3, 8, 7]

 

• heapq.heappop(Heap) - 노드 삭제

>>> heap
[1, 6, 3, 8, 7]
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
3
>>> heap
[6, 8, 7]

 

• heapq.heapify(리스트) - 기존 리스트를 힙으로 변경 

# 기존 리스트 a
>>> a = [5,2,3,1,8,9]

# 리스트 -> 힙
>>> import heapq
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 8, 9]

 

 

최대 힙 만들기

 

파이썬 heapq 모듈은 최소 힙으로 구현 되어있어서 최대 힙 하기 위해서는 y = -x 변환을 해줘야 한다. 

힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선 순위로 힙을 구성한다. 

-item의 형태로 최소 힙 구현을 했기 때문에 최소 힙을 사용해서 최대 힙 구현을 한다.