[Python] 파이썬에서의 우선순위 큐

파이썬 환경에서, 스택이나 큐는 기본 리스트 형태로 구현이 가능하다. 그렇다면 우선순위 큐는 어떻게 만들까?

---

1. heapq를 이용한 방법

사용 조건

import heapq를 상단에 추가한다.

사용 방법

기존에 선언한 리스트로 사용할 수 있다. 리스트에 값을 추가할 때, append메소드 대신 heapq.heappush(list, value)를 사용해 값을 추가하면 최소값 순서로 정렬된 큐를 만들 수 있다.

최대값을 기준으로 정렬하기 위해서는 우선순위를 조절해야 한다. heapq는 기본적으로 value의 값대로 우선순위를 계산하는데, heapq.heappush(list, (priority, value))로 우선순위를 변경할 수 있다. 그러므로 최대값 우선순위 큐를 만들기 위해서는 heapq.heappush(list, (-value, value))로 작성하면 된다.

힙이란?
최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)(#).

메소드

push

heapq.heappush(list, value)
선언한 리스트 list에 대해, 우선순위 큐의 형태를 유지하며 value를 넣는다.

pop

heapq.heappop(list)
list에서 가장 우선순위가 작은 값을 pop한다. 이 때 pop된 값을 리턴 값으로 가진다.
pop하지 않고 값만 확인하고 싶다면 list[0]라고 쓴다.

heapify

heapify(list)
list를 heap으로 변환한다.

예제

프로그래머스-이중우선순위큐(링크)

문제

정답 코드

import heapq

def solution(operations):
    answer = [0,0]
    mn =[]
    mx = []
    
    for op in operations:
        data = int(op[2:])

        if op[0] == 'I':
            heapq.heappush(mn, data)
            heapq.heappush(mx, (-data,data))
        elif op[0] == 'D':
            if len(mn) == 0:
                continue
            
            if data == -1:
                value = heapq.heappop(mn)
                mx.remove((-value,value))
            elif data == 1:
                value = heapq.heappop(mx)[1]
                mn.remove(value)
                
    if len(mx) == 0:
        answer[0] = 0
    else:
        answer[0] = heapq.heappop(mx)[1]
        
    if len(mn) == 0:
        answer[1] = 0
    else:
        answer[1] = heapq.heappop(mn)
            

    return answer

2. PriorityQueue를 이용한 방법

사용 조건

from queue import PriorityQueue를 상단에 추가한다.

사용 방법

list = PriorityQueue() 를 쓰면 list를 우선순위 큐로서 사용할 수 있다. 큐의 max size를 지정하고 싶다면, list = PriorityQueue(maxsize=n) 을 사용한다.

메소드

put

원소 삽입 메소드
list.put(value)
우선순위를 직접 지정하고 싶다면, list.put((priority, value))를 사용한다.

get

원소 반환/삭제 메소드
list.get()
list.get()[1] (우선순위, 값)의 형태로 저장했을 때 사용.