python 우선순위 que vs 힙 자료구조

https://github.com/zinhyeok/algorithm_study/tree/main/priority_que

GitHub - zinhyeok/algorithm_study: 알고리즘 스터디 기록용

문제 

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

위의 최소 힙 문제를 풀던 중 힙 heapq가 기억이 나지 않아서

from queue import PriorityQueue
N = int(input())
pque = PriorityQueue()
for _ in range(N):
    cmd = int(sys.stdin.readline().strip())
    if cmd == 0:
        try:
            print(pque.get())
        except:
            print(0)
    else:
        pque.put(cmd)

로 문제를 해결하려고 했었는데, 시간 초과가 떠서 문제를 해결하지 못했다. 

결국 min_heap으로 문제를 풀었는데 우선순위 que도 내부적으로 heapq로 구현되어있다고 알고 있는데 시간 차이가 나는 이유가 궁금해졌다. 

from heapq import heappush, heappop
import sys
N = int(input())
min_heap = []
for _ in range(N):
    cmd = int(sys.stdin.readline().strip())
    if cmd == 0:
        try:
            print(heappop(min_heap))
        except:
            print(0)
    else:
        heappush(min_heap, cmd)

시간 초과 이유 

아래의 참고 링크를 보니 이유가 잘 정리되어 있었다. 

PrioriryQueue의 경우 thread safe 유효성 검사 과정이 있어 시간이 차이가 났던 것이다. 

thread safe가 뭔데?

스레드 safety를 예전 OOP 수업 때 들었었는데..! 그 기억을 되살려보면 멀티 스레드 프로그래밍에서  공유자원에 여러 스레드로부터 동시에 접근이 이루어졌을 때 프로그램의 실행에 문제가 없도록 하는 방식이었다. 

결론은 왠만하면(thead safety를 신경쓰지 않아도 되는 문제는) heapq로 문제를 해결해보자!

 

참고자료 

https://slowsure.tistory.com/130

[Python/파이썬] PriorityQueue & heapq / 우선순위큐와 힙큐

https://velog.io/@highcho/Algorithm-baekjoon-1927

[Algorithm] 백준 1927 - 최소 힙 in Python(파이썬)