백준 1927 최소 힙, 11286 절댓값 힙 (heapq와 PriorityQueue의 차이)

과정

• heapq와 PriorityQueue를 사용하여 해결할 수 있다.
• queue 라이브러리의 PriorityQueue를 사용했다.
  • maxsize를 설정하면 최대 크기가 설정된다.
• 우선순위 큐는 qsize(길이), put(추가), get(값 반환)의 기능이 있다.
• put을 통해 넣은 값은 우선 순위에 따라 정렬된다. pop은 우선 순위가 가장 낮은 값을 제거하고 반환한다.
  • put((1, "value")) 처럼 튜플로 추가하면, (우선순위, 값) 이 된다.
  • get()[1] 처럼 튜플로 제거하면, 값이 반환된다.

# 1927 최소 힙
import sys
input = sys.stdin.readline

from queue import PriorityQueue
N = int(input())
q = PriorityQueue()

for _ in range(N):
    num = int(input())
    if num != 0:
        q.put(num)
    else:
        if q.qsize() != 0:
            print(q.get())
        else:
            print(0)

• heapq를 사용한 풀이는 다음과 같다.

import sys
input = sys.stdin.readline

import heapq
N = int(input())

heap_q = []
for _ in range(N):
    num = int(input())
    if num != 0:
        heapq.heappush(heap_q, num)
    else:
        if len(heap_q) != 0:
            print(heapq.heappop(heap_q))
        else:
            print(0)

• 튜플로 우선순위와 값을 입력, 제거하는 절댓값 힙 문제

# 11286 절댓값 힙
import sys
input = sys.stdin.readline
from queue import PriorityQueue
q = PriorityQueue()

N = int(input())
for _ in range(N):
    num = int(input())
    if num == 0:
        if q.qsize() != 0:
            print(q.get()[1])
        else:
            print(0)
    else:
        q.put((abs(num), num))

• heapq를 사용한 풀이는 다음과 같다.

import sys
input = sys.stdin.readline

import heapq
N = int(input())

heap_q = []
for _ in range(N):
    num = int(input())
    if num != 0:
        heapq.heappush(heap_q, (abs(num), num))
    else:
        if len(heap_q) != 0:
            print(heapq.heappop(heap_q)[1])
        else:
            print(0)

• PriorityQueue를 사용할 때보다 heapq를 사용할 때 메모리도 적게 사용하고, 시간이 절반으로 감소했다.
  PriorityQueue를 보면 heapq를 사용하는 것 같기에 어떤 차이인지 궁금했다.
  

https://stackoverflow.com/questions/36991716/whats-the-difference-between-heapq-and-priorityqueue-in-python
https://slowsure.tistory.com/130
이 글의 설명에 따르면 PriorityQueue는 thread-safe 하고, heapq는 Non-safe 하다고 한다.
PriorityQueue는 thread-safe 를 확인하는 과정에서 시간이 추가로 걸린다.

Thread-safe는 멀티쓰레드 환경에서 쓰레드가 공유 자원에 동시에 접근해도 제대로 동작하도록 하는 것인데, 이에 관해서는 CS를 공부하며 따로 정리할 예정이다.