우선순위 큐

Goal

1. 우선순위 큐 이해하기
2. 힙(Heap) 자료구조 이해하기

 

우선순위 큐란?

• 높은 우선순위를 가진 원소가 낮은 우선순위를 가진 원소보다 먼저 처리된다
• 파이썬에선 힙(heap)이라는 자료 구조로 구현이 가능하다

Max heap이라면 13이 가장 큰 수로 젤 높은 우선순위를 가지게 되어 젤 먼저 반환된다

 

힙(heap)이란?

• 완전 이진 트리(Complete Binary Tree)로 루트 노드에 있는 값은 트리에서 최대값 (Max Heap) 혹은 최소값 (Min Heap)이다
• 부모 노드의 값이 자식 노드의 값보다 항상 크거나 (Max Heap) 항상 작다 (Min Heap)