[자료구조] 우선순위 큐(Priority Queue/Heapq) 구현 - 파이썬(Python)

우선순위 큐란?

  우선순위 큐는 먼저 들어온 데이터가 먼저 처리되는 일반적인 큐와 달리, 우선순위가 높은 데이터부터 처리되는 자료구조이다. 배열, 연결리스트, 힙(Heap)으로 모두 구현할 수 있지만 일반적으로는 시간복잡도가 적은 힙(Heap)을 사용한다.

 

힙(Heap)

  최솟값, 최댓값을 찾아내는 연산을 빠르게하기 위해 고안된 완전이진 트리의 일종인 자료구조이다. 힙은 최소 힙과 최대 힙으로 구분할 수 있다.

 

- 최소 힙: 루트노드가 가장 작은 값을 가지며, 항상 부모노드는 자식노드보다 작은 값을 가짐

최소 힙 예시

 

- 최대 힙: 루트노드가 가장 큰 값을 가지며, 항상 부모노드는 자식노드보다 큰 값을 가짐

최대 힙 예시

 

우선순위 큐 구현 (파이썬)

- PriorityQueue

from queue import PriorityQueue

pq = PriorityQueue()

pq.put(1)
pq.put(3)
pq.put(2)

pq.get() # 1
pq.get() # 2
pq.get() # 3

- heapq

import heapq

pq = []

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

heapq.heappop(pq) # 1
heapq.heappop(pq) # 2
heapq.heappop(pq) # 3

 

  파이썬 우선순위 큐 구현에서 heapq가 PriorityQueue보다 실행시간이 적게 걸려 heapq를 일반적으로 많이 사용한다. 또, PriorityQueue와 heapq는 최소 힙만 다룰 수 있기 때문에 큰 수부터 pop 하고싶을 때는 - 부호를 붙혀 push하면 된다.

heappush()와 heappop() 모두 O(logN)의 시간복잡도를 갖는다.