[PYTHON] PriorityQueue, heapq

목차

우선순위 큐?

• GREEDY알고리즘 문제는 정렬 아니면 우선순위 큐 문제일 정도로 자주 쓰이는 자료구조.
• 일반적인 QUEUE처럼, 데이터가 들어온 순서대로 나가는 것이 아니라, 우선순위가 높은 데이터가 먼저 출력되는 자료구조.
• 우선순위 큐는 힙으로 구현 가능한데, 최소값 우선큐 = 최소힙 & 최대값 우선큐 = 최대힙
• O(logn) 의 시간복잡도
• PriorityQueue 와 heapq 모두 최소힙( 작은값부터 출력) 만 지원.

queue.PriorityQueue( )

Tip

queue 모듈의 다음과 같은 클래스들 에서, 동일 메소드 사용 가능.

queue.Queue ( maxSize )	기본 큐. FIFO 구조
queue.SimpleQueue	입력 제한 없는 FIFO 큐
queue.LifoQueue (maxSize)	스택. LIFO
queue.PriorityQueue(maxSize)	우선순위 큐. 웃자가 작을수록 높은순위 가짐

 

활용

선언

from queue import PriorityQueue

queue = PriorityQueue()

# 큐의 크기 제한 가능 
max_queue = PriorityQueue( maxsize = 5 )

 

삽입 : put( ) , put_nowait( )

queue.put(1)
queue.put(5)

# put( 우선순위, 값 ) 
queue.put(3,"hello")

queue .put_nowait(2)  #큐가 가득 차면 queue.Full 예외 발생 

put_nowait( ) 이 필요한 이유: put( )을 사용하면 queue가 가득 찼을 경우, 빈자리가 생길 때 까지 무한 대기하다 빈자리 생기면 등록함.

따라서 크기 제한이 있는 queue의 경우, put_nowait( )을 사용

 

우선순위 큰 값부터 반환

# 선언시 튜플 형태로 값을 삽입함 ( - 값 , 값 )

numbers = [2,5,4,1,3,6]
for num in numbers:
	queue.put(-num,num)

 

삭제 (반환 O, 삭제 O ) : get( ) , get_nowait( ) — 작은 값 먼저 반환

queue.get()

queue.get()[1] #튜플에서 값 반환 

queue.get_nowait() #큐가 비었을 우 queue.Empty 예외 발생

get_nowait( ) 이 필요한 이유: 큐에 값이 없을 경우, 무한대기함

 

크기 : qsize( )

queue .qsize()

 

비었는지/ 가득 찼는지 확인 : empty( ) , full( ) - T/F 반환

queue.empty()  # 비었는지 확인

queue.full()  # 찼는지 확인 - maxsize와 원소개수 비교 

 

heapq( ) - 파이썬에서 PriorityQueue() 보다 속도 ↑

삽입/ 삭제 : heappush( ) , heappop( )

import heapq 

queue = []

# 삽입 
heapq. heappush( queue , 10 )
heapq. heappush( queue , 8 )
heapq. heappush( queue , 9 )
print(queue) #[8,9,10]

# 삭제 
heapq. heappop(queue)  #8
heapq. heappop(queue)  #9
heapq. heappop(queue)  #10

 

최소값 구하기 queue[0]

queue[0] #인덱스 통해 접근 

# !주의점! 
# 힙을 사용하여 만들어 졌기 때문에 0번째 요소가 가장 작다고 1번째 요소가 두번째 최소값이란 보장x 
# 왜냐면 원소 삭제시마다 매번 최소값을 0번 인덱스에 재배치 하기 떄문. 

# 그럼 2번째 최소값을 얻으려면? 
# queue.heappop() -> queue[0] 으로 접근해야함

 

기존 리스트 힙으로 변환 heapify()

시간 복잡도 : O(n)

queue = [3,2,4,6,1,5]
heapify(queue) 
print(queue)  #[1,2,3,4,5,6]

 

[응용] 최대힙 생성 : heappush( [리스트명] , ( - num , num ) )

from heapq import heappush, heappop

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heappush(heap, (-num, num))  # (우선 순위, 값)

# 출력 
while heap:
  print(heappop(heap)[1])  # index 1

 

[응용] n번째 최소/최대값 구하기 : nsmallest(개수,리스트) , nlargest(개수,리스트)

총 n개의 최소값이 반환되기 때문에, 마지막 값이 구하고자 했던 값이다.

from heapq import nsmallest
nums = [4, 1, 7, 3, 8, 5]

nsmallest(3, nums )[-1] # [1,3,5][-1] => 5 반환 
nlargest(3, nums )[-1]  # [8,7,5][-1] => 5 반환

 

nsmallest 구현

from heapq import heapify, heappop

def nsmallest(n,nums):
    heapify(nums)
		return [ heappop(nums) for _ in range(n) ]

 

nlargest 구현

from heapq import heapify, heappop
def nlargest (n,nums):
    heap = []
    for num in nums:
        heappush(heap, (-num, num) )
    return [heappop(heap)[1] for _ in range(n)]

 

[응용] 힙정렬

from heapq import heappush, heappop

def heap_sort(nums):
  heap = []
  for num in nums:
    heappush(heap, num)

  sorted_nums = []
  while heap:
    sorted_nums.append(heappop(heap))
  return sorted_nums

print(heap_sort([4, 1, 7, 3, 8, 5]))   # [1,3,4,5,7,8]

 

 

 

참고 :

파이썬의 heapq 모듈로 힙 자료구조 사용하기 | Engineering Blog by Dale Seo

[Python] 우선순위 큐(PriorityQueue) 사용 방법 - 지니의 기록 (tistory.com)

[Python:자료구조] 파이썬 큐(Queue) , 우선순위 큐(PriorityQueue) 사용방법 및 예제 총정리 - 정보의 공유 사회 (tistory.com)