HEAP #힙 자료구조 #heapq #Dijkstra #다익스트라 알고리즘

힙이란?

: 무엇인가를 차곡차곡 쌓아올린 더미

: 항상 이진트리 형태

: 부모의 값은 항상 자식의 값보다 크거나(최대 힙) 작아야(최소 힙) 함

 

• 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
• 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙

 

# 파이썬에서 heap 사용하기 

# 최소 힙 구현과 heapq 모듈 사용

import heapq  #heapq 

heap = []                     #list로 초기화

heapq.heappush(heap, item)    #item을 heap에 추가 >> heap에 push하면 자동으로 최소힙의 형태로 정렬

heapq.heappop(heap)           #heap에서 가장 작은 원소를 pop

heapq.heapify(lst)            #리스트 lst를 heap으로 변환

 

* 힙은 최소값을 빨리 찾기 위함이지 정렬이 아님을 주의

 

 

# 최대 힙 구현

heap = [1, 2, 3, 4]

max_heap = []

for i in heap:
	heapq.heappush(max_heap, (-i, i))       #거꾸로 push
                                               #[(-4, 4), (-3, 3), (-2, 2), (-1, 1)]

heapq.heappop(max_heap)                        #최댓값이 반환됨    >> 4

 

 

 

 

다익스트라 알고리즘이란?

: 그래프 꼭짓점 간의 최단 경로를 찾는 알고리즘

: 가장 짧은 경로를 찾는 알고리즘  =  최단 경로 트리

 

import heapq
import sys

n, m = map(int, input().split())    #n: 노드 개수,   m: 간선
k = int(input())                    #시작 노드
INF = sys.maxsize                   #1e8

graph = [[] for _ in range(n+1)]

distance = [INF] * (n+1)            #간선 가중치 초기화

for _ in range(m):
	u, v, w = map(int, input().split())     #u:출발노드, v:도착노드, w:간선 가중치
    graph[u].append((v, w))                 #graph에 도착과 가중치 입력
    
def dijkstra(start):
	q = []
    heapq.heappush(q, (0, start))    #최소 힙, 우선순위를 지키며 정렬 됨
    distance[start] = 0              #거리 값
    
    while q:
    	dist, now = heapq.heappop(q)   #우선 순위가 가장 낮은 값이 나옴 (= 가장 작은 거리)
        
        if distance[now] < dist:       #현재 노드까지의 거리보다 작으면 continue
        	continue
            
        for i in graph[now]:
        	if (dist + i[1]) < distance[i[0]]:     #기존 보다 값이 작으면
            	distance[i[0]] = dist + i[1]       #현재 거리에 가중치 더해줌
                heapq.heappush(q, (dist + i[1], i[0]))   #q의 거리 값 갱신
                
dijkstra(k)