Priority Queue

우선순위큐란?

데이터 구조의 일종으로 항목들이 우선순위에 따라 저장되고 접근되는 자료구조다. 일반적인 큐(Queue)는 FIFO 원칙에 따라 동작하지만, 우선순위 큐에 각 항목은 우선순위 값과 함께 저장되며, 우선순위가 높은 항목이 우선적으로 처리되는 자료구조이다.

우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.

힙이란?

힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조다.

힙의 종류

최대 힙(Max Heap)
노드중 가장 큰 값이 root에 위치하며, 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리

최소 힙(Min Heap)
노드중 가장 작은 값이 root에 위치하며, 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리

힙의 특징

• 빠른 삽입과 삭제 O(log N)의 시간 복잡도
• 우선순위 관리
• 효율적인 우선순위 추출 (root노드는 O(1)의 복잡도)

우선순위큐의 연산

• 삽입
• 삭제
• 우선순위 변경
• 최상위 항목 조회

시간 복잡도(Time complexity)

Operation	Average	Worst
Access	O(1)	O(1)
Search	O(N)	O(N)
Insert	O(log N)	O(log N)
Delete	O(log N)	O(log N)

Python에서의 우선순위 큐(예시)

파이썬에서는 Queue를 통해 우선순위 큐를 지원한다.

pq = PriorityQueue()
pq.put(6)
pq.put(10)
pq.put(-5)
pq.put(0)
pq.put(8)
while not pq.empty():
    # 작은 수부터 빠짐
    print(pq.get())

그렇지만 위 방식은 thread-safe라는 추가적인 기능을 제공한다. 따라서 다음과 같이 heapq를 사용하여 구현하는 것이 시간이 중요한 코딩테스트에선 더 효율적이다.

import heapq as hq

pq = []
hq.heappush(pq, 6)
hq.heappush(pq, 12)
hq.heappush(pq, 0)
hq.heappush(pq, -5)
hq.heappush(pq, 8)
print(pq)
while pq:
    print(pq[0]) # 최상단 노드 값
    print(hq.heappop(pq)) # 반환 값 동일

Priority Queue의 사용 예시

• 작업 스케줄링(Job Scheduling)
• 다익스트라 알고리즘(Dijkstra's Algorithm)
• 허프만 코딩(Huffman Coding)
• 이벤트 처리(Event Handling)