파이썬 - 우선순위 큐

우선순위 큐

큐(Queue)는 선입선출의 자료구조이다. (선입후출은 스택(Stack))

우선순위 큐(Priority Queue)는 말 그대로 우선순위가 높은 자료가 먼저 나가는 큐를 말하는 것이다.

파이썬에서는 우선순위 큐를 구현하기 위해 일반적으로 힙큐(heapq)를 사용한다.

힙큐

힙은 완전이진트리를 기반으로한 자료구조이다.

힙큐는 기본적으로 가장 작은 숫자가 먼저 나오는 최소힙의 구조를 하고있다.

힙 활용

import heapq


N_list = [] # 리스트 선언

heapq.heapify(N_list) # 리스트를 힙큐로 변환

heapq.heappush(N_list,40) # 힙큐에 40을 추가

result = heapq.heappop(N_list) 
# 힙큐에서 가장 작은 원소를 제거하고 반환

최대힙 만들기

import heapq

N_list = [10,30,20]

heapq.heapify(N_list)

max_N_list = []

for i in N_list:

    heapq.heappush(max_N_list, (-i,i))


print(max_N_list)

가장 작은 값에 부호를 바꾸면 가장 큰 값이 된다는 것을 활용하여 (-i,i)의 튜플을 힙큐에 저장하는 방식으로 최대힙을 만들 수 있다.

이렇게 만든 최대힙을 사용할 때는 튜플의 두번째 원소를 호출하여야 한다.

result = heapq.heappop(max_N_list)[1]