파이썬 우선순위 큐, 힙

우선순위 큐(Priority Queue)

• 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조
• 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조
• 일반적으로 heapq로 구현

 

 

파이썬 라이브러리  PriorityQueue

•  파이썬 우선순위 큐 구현에서 heapq가 PriorityQueue보다 실행시간이 적게 걸려 heapq를 일반적으로 많이 사용
• 또, PriorityQueue와 heapq는 최소 힙만 다룰 수 있기 때문에 큰 수부터 pop 하고싶을 때는 - 부호를 붙혀 push
• heappush()와 heappop() 모두 O(logN)의 시간복잡

q = PriorityQueue()
q.put((0,k))
distance[k] = 0
 current = q.get()
 q.put((distance[next], next))

 

힙(heapq)

• 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조
• 최소 힙 : 부모 노드의 값(key 값) ≤ 자식 노드의 값(key 값)
• 최대 힙 : 부모 노드의 값(key 값) ≥ 자식 노드의 값(key 값)

q = []
heapq.heappush(q, (0, start))
distance[start] = 0

dist, now = heqpq.heappop(q)
 heapq.heappush(q, (cost, i[0]))

 

 

[1753번] 최단경로 구하기 (다익스트라, 우선순위큐, 힙)