작성: 202422145 박성수

3주차는 2주차에 배운 트리의 성질을 활용한 힙 트리(Heap Tree)를 통해 우선순위 큐(Priority_queue)를 사용하는 방법을 학습한다. 또한 이전에 배운 BFS와 우선순위 큐를 사용하여 최단 경로를 구하는 알고리즘은 다익스트라(Dijkstra) 알고리즘과 3중 for문으로 최단 거리를 구하는 플로이드-워셜(Floyd-Warshall) 알고리즘을 학습한다.

1. Heap

Heap은 항상 완전 이진 트리의 형태를 띠고 있고, 종류에 따라 부모가 자식보다 항상 크거나 작아야 한다.

Heap은 최댓값 또는 최솟값을 찾는 시간복잡도가 O(1)이고 새로운 값을 삽입하거나 기존의 값을 제거하는 시간복잡도가 O(logN)인 굉장히 빠른 자료구조이다.

다음은 최소 힙이 작동하는 방식이다.

1-1. 데이터 삽입

1. 가장 끝에 새로운 노드를 삽입
2. 그 노드와 부모 노드의 값을 비교
3. 두 노드가 규칙에 서로 어긋난다면 부모 노드와 교환 (부모 노드는 현재 노드 인덱스에 /2를 하면 됨)
4. 조건에 맞을 때까지 반복

1-2. 데이터 삭제