Python3 | 파이썬에서 우선순위큐(heap)를 사용하자 (heapq 사용법)

 우선순위큐, 흔히 힙이라고 하는 자료구조도 코딩테스트에서 나름 자주 등장하는 아이들이다. 직접 힙을 만들어서 사용할 수도 있지만 더 많은 시간이 소요되니 파이썬에서 제공해주는 패키지를 활용하자. 파이썬에서 우선순위큐를 이용하기 위해서는 PriorityQueue와 heapq를 사용할 수 있는데 이 포스팅에서는 heapq의 간단한 문법만 기록할 것이다.

 

import heapq

q = []

heapq.heappush(q, 1)
heapq.heappush(q, 3)
heapq.heappush(q, 2)

heapq.heappop(q)
heapq.heappop(q)
heapq.heappop(q)

  사용법은 아주 간단하다. 일단 heapq를 import해주고, 리스트를 하나 선언해준다. 그리고 [code]heapq.heappush[/code]를 통해서 하나 씩 요소를 집어넣어준다. 하나 씩 꺼내고 싶을 때는 [code]heapq.heappop[/code]을 이용해준다. 이 때, 꺼내고 싶지는 않고 접근만 하고 싶으면 index로 접근해주면된다. (heapq는 힙 자료구조 자체를 만들어준다기 보다, 리스트를 힙처럼 활용할 수 있도록 한다고 보면 된다.)

 기본적으로 heapq는 (PrioirtyQueue도 마찬가지지만) MinHeap으로 작동한다. 그래서 MaxHeap으로 작동시키고 싶으면, 부호를 반대로 붙여줘서 활용하면 된다!