✅우선순위 큐

✔우선순위 큐란?

• 큐나 스택과 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있다.
• 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다.
• 같은 우선순위를 가진다면, 먼저 들어온 원소를 처리한다.
• 우선순위 큐는 힙(heap)이라는 자료 구조를 통해 구현할 수 있다.
• 시간복잡도는 O(logN)이다.

✔힙이란?

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

heapq

• 파이썬에서는 우선순위 큐를 부모 노드 값이 항상 자식 노드들의 값 보다 작은 Min Heap을 사용한다.
  root 노드의 값이 가장 작다.
• queue의 PriorityQueue보다 heapq가 처리속도가 빠르므로 heapq를 사용한다.
• heapq 리스트의 0번째 인덱스에는 항상 root 노드의 값이 들어간다.

👉heapq 사용법

• 먼저 빈리스트를 만든다. pq = []
• heapq.heappush(pq, 123) // pq에 값을 넣는 메서드
• heapq.heappop(pq) //pq에 값을 빼는 메서드
  heappop()메서드 사용시, heapq에 root노드 값이 삭제된다.

👉heapq 예시

import heapq

pq = []
heapq.heappush(pq, 6)
heapq.heappush(pq, 12)
heapq.heappush(pq, 0)
heapq.heappush(pq, -5)
heapq.heappush(pq, 8)
print(pq)
while pq:
    print(pq[0])		//root 노드 출력
    heapq.heappop(pq)	//root 노드 삭제

[-5, 0, 6, 12, 8]
-5
0
6
8
12