MJay
[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)
'PSU > CSE 565 - Algorithm' 카테고리의 다른 글
[CSE 565] - 2019-10-09 - Matroid (0) | 2019.10.10 |
---|---|
[CSE 565] - 2019-10-02.pdf leftist tree (0) | 2019.10.10 |
[CSE 565] - 2019-10-07.pdf 일단 오늘꺼 정리 (0) | 2019.10.09 |
[CSE 565] - 2019-10-07.pdf (0) | 2019.10.09 |
[CSE 565] - 2019-10-07.pdf (0) | 2019.10.09 |