[파이썬] PriorityQueue, heapq

큐 관련 파이썬의 모듈

PriorityQueue

• 데이터를 추가한 순서대로 제거(FIFO, 선입 선출)되지 않음
• 우선순위가 가장 작은 값 부터 제거됨 -> 내부적으로 데이터를 정렬된 상태로 보관한다는 의미, heap 모듈로 구현되어 있음

from queue import PriorityQueue
que = PriorityQueue(maxsize=8)
que.put(4) # 원소 추가
que.get() # 원소 삭제
que.put((3, 'apple')) # (우선순위, 값)의 튜플 형태로 데이터를 넣으면 우선순위 기준으로 데이터가 정렬됨
que.get()[1] # 값 반환

 

heapq 

• 최소 힙(min heap) 형태가 유지되는 자료구조
  -> 가장 작은 값은 언제나 인덱스 0 (이진트리의 root)에 위치함, 부모 노드는 항상 자식 노드보다 작거나 같도록 원소가 추가되고 삭제됨
• 원소들이 항상 정렬된 상태로 추가, 삭제됨
• heappush() : 이진 트리에 원소를 추가하는 함수, O(logN)
• heappop() : 이진 트리에서 원소를 제거하는 함수, O(logN)
   -> 가장 작은 값 (이진 트리의 루트, 리스트의 0번째 인덱스)이 제거된 후 그 다음으로 작은 값이 그 자리로 올라옴
  -> 즉 heappop()으로 원소를 삭제할 때마다 이진 트리의 재배치를 통해 매번 새로운 최소값을 인덱스 0에 위치시킴
  -> 따라서 두 번째로 작은 원소를 얻으려면 바로 heap[1]으로 접근하면 안 됨
• heapify() : 이미 원소가 들어있는 리스트를 최소힙으로 만드는 함수, O(N)
  -> 리스트 내부 원소들이 힙 구조에 맞게 재배치됨

from heapq import heappush, heappop, heapify
# 내장 모듈이므로 파이썬만 설치되어 있으면 간단하게 임포트하여 힙 함수 사용 가능
# heapq는 PriorityQueue처럼 리스트와 별개의 자료구조가 아님. 리스트를 마치 최소 힙처럼 다룰 수 있게 해주는 모듈
# 빈 리스트를 생성해놓은 다음 heapq 모듈의 함수를 호출할 때마다 이 리스트를 인자로 넘겨야 함
# 즉 파이썬에서는 heapq 모듈을 통해 원소를 추가, 삭제한 리스트가 최소 힙

heap = [] # min heap 생성
heappush(heap, 4) # 원소 추가
heappush(heap, 3)
heappush(heap, 9)
heappush(heap, 1)
print(heap) # [1, 3, 4, 9]

heappop(heap) # 원소 삭제
print(heap) # [3, 4, 9] <- 가장 작은 값이 삭제됨, 그 다음으로 작은 3이 인덱스 0으로 올라옴

heap[0] # 원소 읽기

nums = [4, 1, 7, 3]
heapify(nums)
print(nums) # [1, 3, 4, 7] <- 기존 리스트가 최소힙으로 변환됨

 

heapq를 최대힙으로 사용하려면 튜플을 쓰면 된다.

• (우선 순위, 값)을 원소로 취하여 각 값에 대한 우선순위를 부여하면 튜플의 앞에 있는 값 기준으로 최소 힙이 구성된다.
• 따라서 우선 순위를 음수로 설정하면 최대 힙으로 사용 가능

from heapq import heappush, heappop
heap = []
nums = [4, 1, 7, 3, 8, 5]

for i in nums:
	heappush(heap, (-i, i)) # (우선 순위, 값)
    
while heap:
	print(heappop(heap)[1]) # [8, 7, 5, 4, 3, 1]

 

 

ref:

https://docs.python.org/ko/3/library/heapq.html