알고리즘 시험 준비 - [11/13 Files] - 2019-10-02

 

일단 하나씩 적어보자

 

PQ는 V- Ak* 속하지 않는 Vertices를 가지고 있다. 

 

dist(u) 는 s to v로 가는 length를 가지고 있다. 그리고.그리고 그건 A*k에 속하는 Vertecies를 통해서다. 

 

V * 가 PQ에서 사라지는 순간 -> dist(v*)와 s에서 v*로 가는 거리가 같아진다. 

 

그 다이 스트라에서 weight를 뜻하는 거 같네 별 의미가 없는 거 같은데

 

그냥 문제를 얼른 풀어봐야겠다.

 

Running Time은 

 

Delete Min에서 VlogE

 

Decrease Key에서 ElogV

 

(V+E) logV

 

이제 Binary Heap을 사용하여 구현을 할 수도 있다.

 

Heap은 min-heap 이랑 max-heap을 사용할 수 있다. 

 

이게 쉬운 거니 넘어가자 

 

 

이건 뭐 당연한 건데 좀 봐야 할 거는 bubble-up이다

 

lognlogn이다. 

 

 

sift-down이라고 부른다. shift인 거 같은데 그건 아니 거 같다. 

 

insert를 하면 bubble-up 이 일어나니 O(logn)

 

decrease-key를 하면 bubble-up 이 일어나니 O(logn)

 

delete-min 은 siftdown이라서 O(logn)이다.logn 

 

 

Binary Heap을 Merge 하는 건 O(n) 물론 그야 당연한 거 같다.

 

Leftist tree는 rank(v), 즉 number of nodes on the shortest path from v to NULL

 

즉 shortest path로 가는 node의 개수가 왼쪽이 더 많다는 거구나 왼쪽의 child 가 number of nodes가 더 많구나. 그렇다고 왼쪽의 node가 많은 거는 아니다. 

 

rank(L(v)) >= rank(R(v))

 

rank(root) = O(logn) 

 

당연히 level 별로 1개만 지나가기 때문이다. 

 

 

Merging two leftist trees 

 

일반적으로는 O(n)이지만 이 경우 O(logn)만큼 걸린다 

 

Merge를 하는 과정에서 Rank를 Update를 하구나 

 

left child와 right child끼리 비교하면서 rank를 업데이트를 하는 거 같다. 

 

find-min -> return root

 

delete-min -> 

merge TL(root), TR(root)?? left subtree of root 랑 right subtree root 랑 merge를 해서 Delete-min을 하나보다.  왼쪽과 오른쪽을 머지한다. 그 과정에서 check 하고 swap을 하여 rank를 업데이트를 한다고 보면 된다. 

 

insert(PQ, key) 

 

merge(PQ, a new tree with the new node)

 

decrease-key -> 

 

1. cut off subtree rooted at x Tx

2. adjust the remaining

3. merge Tx and the adjusted T

 

Tx -> x에서의 subtree를 뜻하는 거 같다. 

 

이거 다시 보니까 일단 Tx 쪽을 잘라서 Rank를 업데이트하고 다시 Merge를 하는 거구나 

 

decrease-key가 많이 복잡하네

 

rank left가 더 작으면 

 

left의 rank를 업데이트해준다고 보면 된다.