[자료구조] 우선순위 큐 (파이썬 heapq 사용법)

queue란?

큐는 가장 먼저 삽입된 데이터를 가장 먼저 삭제하는 FIFO(First in First out) 자료구조형이다. rear(한쪽 끝)에 데이터가 추가되고,
front(다른쪽 끝)에서 데이터가 삭제되는 방식이다.

heap이란?

완전 이진 트리

우선순위 큐를 구현하기 위해서는 다양한 자료형을 사용할 수 있는데 그 중 힙은 완전 이진 트리를 기반으로, 삭제 / 삽입에 O(log n) 소요되어 효율적으로 구현할 수 있다.
최소 힙 또는 최대 힙으로 나뉘며, 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 값을 가지는 구조이다.
파이썬의 heapq 라이브러리는 최소 힙을 사용해서 priority 값이 낮을수록 먼저 삭제 된다.

 

---

우선순위 큐

heap 힙 자료구조는 우선순위 큐를 구현하기 위해 사용하는 자료구조이다.

우선순위 큐는 우선순위에 따라 큐에 데이터가 저장되기 때문에, 우선순위가 가장 높은 데이터를 가장 먼저 삭제하게 된다.

따라서 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.

 

heapq 라이브러리 - 파이썬에서 우선순위 큐 사용하기

예를 들어 물건 데이터가 존재할 때, 튜플 (가치, 무게) 데이터로 묶어서 우선순위 큐 자료형에 넣을 수 있다.

이 때 튜플의 0번째 요소가 우선순위의 기준이 된다.

 

최단경로를 찾는 다익스트라 문제에서 우선순위 큐를 사용하려면 현재 노드에서 가장 가까운 노드를 저장하기 위한 목적으로 우선순위 큐를 사용할 수 있다. 우선순위 큐에 거리가 짧은 노드 순서대로 저장한 후, 노드를 하나씩 heappop하며 다른 노드들과의 거리 또한 갱신한다.

---

예시) 한 노드를 기준으로 다른 노드들까지의 최단 경로 구하는 문제 - 다익스트라

# 다익스트라 알고리즘 - 최단경로

import heapq
V, E = map(int, input().split())
start = int(input())
# 연결정보 - 2중 리스트는 느리다.
graph = [[] for _ in range(V+1)]
distance = [int(1e9) for _ in range(V+1)]

for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v,w))

def dijkstra(start):
    cost = []
    heapq.heappush(cost, (0, start))
    while cost:
        dist, cur = heapq.heappop(cost)
        if distance[cur] < dist:
            continue
        for node in graph[cur]:
            # node : 현재 노드와 인접한 노드, 비용
            if dist + node[1] < distance[node[0]]:
                distance[node[0]] = dist+node[1]
                heapq.heappush(cost, (dist+node[1], node[0]))

dijkstra(start)

for i in range(1,V+1):
    if i == start:
        print(0)
        continue
    print(distance[i]) if distance[i]!=int(1e9) else print('INF')

 

=> 백준 1753번 문제의 답인데, 시간 초과가 나서 우선순위 큐를 사용해도 문제가 있었나? 싶었는데 input => sys.stdin.readline으로 고치지 않아서 시간초과 나는 거였다.