Priority Queue & an Application

Priority Queue란?

• 일단 queue. 근데 우선순위가 존재한다.
• 우선순위가 높은 노드부터 나오는 것
• 한 마디로 1등만 조진다 !!

Heap Structure

• complete binary tree
  • 왼쪽부터 다 채워져 있다. 
• child 간의 순서는 없고, parent > child 의 순서만 맞춘다. 

인덱스 i의 오른쪽 child : 2i

인덱스 i의 왼쪽 child : 2i + 1

 

heap insert

먼저 모양만 맞춘 상태로 insert > 가장 마지막 노드에 insert 한다.

빨간색 부분에 노드 x를 새로 insert 한다.

if) x < c

일단 x와 c를 바꾼다.

x와 c의 자리를 바꾸게 되면 위와 같은 그림이 되는데, 원래 c < b였으므로 x < b는 당연히 성립한다.

→ x와 a의 관계가 문제

 

하지만 상관없다! 또 비교해서 x > a라면 자리를 바꾸면 그만이다.

insert solution이 위와 같은 방법으로 가능한 이유는 문제 가능 위치가 올라가기만 할 뿐, 그 개수가 늘어나지 않기 때문 이다.

 

heap delete

특정 노드를 delete하게 되면, 먼저 모양을 유지시키기 위해 가장 마지막 노드를 root로 끌어올려 온다.

계속해서 모양을 유지시킨 뒤 문제를 제거하는 방향으로 움직인다. 

if) x > b or c

heap의 특징 중 하나는 child간의 순서가 없다는 것이었다.

그렇다면 x가 내려가야 하는 문제 상황에서 b,c 중 작은거와 교환하는 것이 합리적이다. (다른 하나와의 관계는 자연스럽게 성립되므로)

위 case는 c < b. c와 x를 바꿔도 애초에 c < b였으므로 c와 오른쪽 child인 b의 관계는 성립한다.

 

그 다음은 insert와 상황이 같다. 

x와 ?, a 간의(x와 child의) 관계를 파악한 뒤 내려가야 하면 바꾸고, 아니면 멈춘다.

이 또한 문제 가능 위치가 올라가기만 할 뿐, 그 개수가 늘어나지 않기 때문에 가능한 방법이다. 

 

heap conclucion

• AVL, 2-3 Tree 등 보다 훨씬 빠르고 컴팩트하다.
• sorting은 N * logN보다 빠를 수 없다는 증명이 가능하다.
  • heap(priority queue)는 sorting이 가능하다 : 다 넣고 다 꺼내기..
    • priority queue 작업이 logN보다 빠르면 sorting이 N * logN보다 빠르게 된다.
    • 이 말이 불가능함
    • ∴ N * logN보다 빠르게 sorting할 수 없다. 
      => 다시 찾아봐야 할 듯 

shortest path problem

S -> P 까지가 shortest path 라면 모든 중간지점도 shortest path 이다.

∵ 중간에 다른 shortest path 가 있을 시 그걸로 바꾸면 S -> P가 더 짧아지기 때문 (모순) 

 

Dijkstra Algorithm

• red set: shortest path로 결정된 노드set
• blue set: 아직 모르는 노드set. 각각 red만 지나서 본인으로 오는 shotest path를 알고 있다. 

 

• blue set중 가장 작은 노드(v)를 찾는다.
• 해당 노드를 red로 바꾼다.
• 바꾸어진 노드(v)와 directly connected된 노드만 update 해준다.
• 계속해서 가장 작은 blue set을 비교해 red로 바꿔준다. 

performance comparison

• heap이 없다면, minimum을 찾는 시간은 O(M)이다.
  > 다익스트라는 최소 O(MN)
• heap이 있다면, minimum을 찾는 시간은 O(logM)이다.
  > 다익스트라는 O((N+M)logM) 시간이 걸린다.