yoon's Devlog

우선순위 큐는 각 원소들이 우선순위를 가지고 있고, 높은 우선순위의 원소가 낮은 우선순위의 원소보다 먼저 처리된다. 만약 우선순위가 동일하다면 먼저 들어온 원소를 처리한다. 우선순위는 힙을 통해 구현할 수 있다고 한다. 힙은, 완전 이진 트리로 부모 노드의 값이 항상 자식 노드보다 값이 작거나 큰 트리를 말한다. 부모 노드의 값이 항상 자식 노드보다 작은 경우를 최소힙(Min Heap)이라고 하며, 반대로 부모 노드의 값이 항상 자식 노드보다 큰 것은 최대 힙(Max Heap)이라 한다. 파이썬에는 Priority Queue와 heapq 내장 모듈이 있는데 오늘은 heapq에 대해 살펴보자. heapq는 최소 힙 구조이고, 가장 작은 요소가 0번째에 위치한다. 또한 모든 k에 대해 heap[k]