[CSE 565] - 2019-10-02.pdf Binary Heap

CSE 560 을 봐보자 

 

2019-10-02.pdf

 

PQ stores the vertices in V - Ak* (전체에서 A를 뺀 것)

 

Ak* = {V1*, V2*, Vk*}

 

ak가 아마 s 랑 v 랑 다 같이 Ak에 속한다고 일단 생각하자 

 

 

V* 가 PQ 로 부터 지워지면 - dist(v*) = distance (s, v*)

 

v1, v2, v3, v4, v5

 

지금 이게 뭐를 하고있지?

 

Binary Heap 을 얘기하는 건가? 

 

그냥 그래프를 그려볼까 

 

 

Binary-Heap 은 

 

find-min -> O(1) min heap 

 

delete min, decrease-key, insert -> log(n)

 

# times -> delete min, find-min, insert - Vertex 랑 관련이 있고

 

decrease-key 는 Edge랑 관련이 있다. 

 

 

 

 

Index 가 1부터 시작하는 걸 시작

 

 

heapify 하는 거임 

 

 

sift-down 인듯 

 

 

log(n) 당연한거고 O(1)