[자료구조] Priority Queue & Application

• 본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다.
• 따라서 완벽하지 않은 부분이 있을 수 있습니다.
• 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다.

---

Priority Queue

• 내부 item들이 우선순위를 가진다. 보통 우선순위는 여러 기준이 있지만 최대한 Simple하게 설정해놓는 것이 학습에 용이하다.
• Queue에서 가장 우선순위가 높은 것이 나온다. (우선순위 변동은 없다.)
• 우선순위에 의해 정렬되어 있으면 : Del는 빠르지만, Insert는 느리다.
• 우선순위에 의해 정렬되어 있지 않으면 : Del은 느리지만, Insert는 빠르다.

---

어떤 자료구조를 활용해 구현할까

• 기본 BST를 제외한 AVL, 2-3, 2-3-4, Red-black tree 활용을 생각해보자.
• logN : insert / logN : delete
• 충분히 좋은 자료구조지만, 더 좋은 구조가 없을지 생각해보자
• Heap?

---

Heap

• 완전한 binary tree : 모든 레벨은 마지막 레벨을 제외하고는 가득 채워져있고, 마지막 레벨도 왼쪽부터 순차적으로 채워져 있다.
• 부모는 무조건 자식보다 작은 key값을 보유한다. 왼쪽 자식과 오른쪽 자식에 특별히 차이는 없다. (large flexibility)
• 제일 작은 값은 root에 존재하고, 내려갈수록 값이 커지게 된다.

---

Tree를 표현하는 특이한 방법

• Array로 표현
• root는 index 1에 위치하고 left childe는 2i, right child는 2i+1에 위치한다.

---

Heap insert / delete

• insert : 일단 삽입 후 부모가 현재 노드보다 더 크다면, 위치를 바꿔준다. 해당 작업을 조건이 깨지지 않을 때까지 반복한다. 이러한 과정을 'up-heap'이라고 한다.
• delete : root의 값을 delete하고(가장 작은 키값 내보내기) 제일 밑의 레벨 오른쪽 값을 root로 가져온다. 그리고 root의 자식 둘 중 작은 것과 교환, 이를 반복한다. (조건이 깨지지 않을 때까지). 이러한 과정을 'down-heap'이라 한다.

---

결론

• heap은 insert, delete 모두 O(logN)으로 처리가 가능하다.

---

Shortest path problem

• source 노드에서 전체 나머지 노드를 전부 가는 길 중 가장 짧은 길이 (path가 아닌 길이만)

---

Dijkstra Algorithm

• Red set : 가장 짧은 길이라고 판단이 끝난 노드의 집합
• Blue set : Red set에 포함된 노드만 거쳐서 가는 가장 짧은 거리를 알고 있는 노드의 집합. Red set만으로 도착이 불가능하다면 무한대로 표기한다.
• Round : Blue 중 가장 작은 노드를 탐색하고, Red set으로 편입한다. 그리고 Blue set의 값을 업데이트 한다.
• Red-set만 거쳐 나오는 순간 답이 있어야 한다. blue-set 중 가장 작은 것이 정답이 된다.

---

Dijkstra Algorithm & Heap

• Blue 노드 중 가장 작은 값을 찾아야 한다.
• Red로 편입 후 나머지 노드를 업데이트 해야한다.
• heap을 사용할 경우 이 두 과정이 모두 편리해진다.
• Heap을 사용하지 않을 경우 전체시간은 O(MN)이다. Minimum을 찾는 과정이 n번 필요하기 때문이다.
• Heap을 사용할 경우 전체시간은 O((N+M)logM)이다.