[Python] 파이썬 우선순위 큐(Priority Queue)

우선순위 큐 (Priority Queue)

 

✔  우선순위 큐?

큐와 스택이나 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있는 큐이다. 우선순위 큐에서 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진다면, 먼저 들어온 원소를 처리한다. 

 

우선순위 큐는 힙(Heap)이라는 자료 구조를 통해 구현이 가능하다. 

 

우선순위 큐는 최소한 두 가지 연산이 지원되어야 한다. 

• 하나의 원소를 우선순위를 지정하여 추가하는 함수 (Push)
• 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 반환하는 함수 (Pop)

 

✔  힙(Heap) 이란?

완전 이진 트리(Complete Binary Tree)로, 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 한다. 힙은 우선순위 큐를 구현하거나, 힙 정렬을 하는데 사용된다. 루트 노드에 있는 값이 최대값, 혹은 최소값이며, 자식 노드들의 값의 위치는 기본적인 조건만 맞추면 된다. 

 

최대힙

최소힙

 

✔ 우선순위 큐의 Push

• 맨 끝 위치에 값을 저장
• 부모 노드와 비교하며, 조건을 만족하는 지 확인
  • 만족하지 않는다면, 서로 위치를 변경

✔우선순위 큐의 Pop

• 가장 우선순위가 높은 값을 삭제
• 맨 끝의 노드를 비어있는 루트 노드로 끌어옴
• 루트 노드의 자식 노드들과 값을 비교, 위치 변경
  • 위치를 만족할 때까지 자식 노드와 위치를 변경하며 올바른 위치까지 이동

 

참조 https://velog.io/@mein-figur/Python%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-heapq