[python] 우선순위 큐 PriorityQueue VS heapq

⭐️ 1. 우선순위 큐?

우선순위가 높은 데이터가 먼저 나가는 (제일 위에 놓임) 큐

즉, 제일 첫번째 원소가 제일 우선순위가 높은 것

 

구현 방식

- Heap, List, ... 등 구현 방식이 있다.

 

시간복잡도에 차이가 존재한다.

List의 경우

삽입: O(1), 삭제: O(N)

 

Heap의 경우

삽입: O(logN), 삭제:O(logN)

 

✅ 사용 예시

- 스케줄링, 사건 시뮬레이션, 우선순위에 따른 검색, 정렬 등

 

✅ 규칙 (최소 힙 기준)

• 부모가 두 자식보다 더 작은 수임이 보장된다. (부모가 min)
• 완전 이진 트리를 만족한다.

최소 힙

 

✅ 동작 (회소 힙 기준)

추가 (push) 동작

- 맨 마지막 원소로 추가한다

- 해당 위치에서 root까지 순회하며, min heap을 만족하는지 체크한다

 

시간복잡도: O(logN)

 

 

 

삭제 (pop)

- 맨 앞 원소를 삭제한다

- 빈 맨 앞 원소를 '제일 마지막 원소'로 채워준다 (마지막 노드 삭제)

- 새로운 root부터 시작하여, 재귀적으로 두 자식과 비교하여 min 값을 자신과 교체함

 

시간복잡도: O(logN)

 

 

---

⭐️ 2. PriorityQueue 

- 파이썬의 우선순위 큐 구현체 (모듈)

- 이진 트리 형태

- 최소 힙

    - 부모 노드 값 <= 자식 노드의 값

 

✅ PriorityQueue생성 (instance)

from queue import PriorityQueue
pq = PriorityQueue()

 

• PriorityQueue 클래스 instance 사용

 

 

그럼 pq에 원소를 집어넣고, .. 하기 위해

 

PriorityQueue class의 method를 보자!

 

 

✅ 주요 메소드 (PriorityQueue) - 직접 호출 X

def _put(self, item):
        heappush(self.queue, item)

def _get(self):
        return heappop(self.queue)

- 원소 추가: pq._put()

- 원소 삭제: pq._get()

 

Ququq Class를 상속받는 PriorityQueue Class

 

 

✅ 주요 메소드 (호출 흐름)

🙋‍♀️ PriorityQueue의 _put을 부르면 되겠구나?

 

그런데,

_put 메소드는 private method 이므로 (method 앞에 _ 붙으면 private method)

pq._put() 으로 바로 호출할 수 없다 ! 

(사실 부를 수 있긴 하다)

 

 

🙋‍♀️ PriorityQueue의 부모인 Queue Class의 put을 부르면 되겠구나?

맞다!

PriorityQueue의 부모 클래스의 메소드도 사용 가능하므로,

Queue의 put을 부르면 된다.

 

 

🙋‍♀️ 그럼 heapify는 언제 되는거지?

 

Queue class의 put 메소드를 살펴보자.

 

put 함수 내부에서 _put 매소드를 부른다.

이때 Queue에도, PriorityQueue에도 둘 다 _put 메소드가 존재한다.

 

이때 메소드 오버라이딩에 의해,

PriorityQueue의 _put 이 우선순위가 더 높기 때문에, 

PriorityQueue의 _put이 불리게 된다!

 

PriorityQueue의 _put에서는 heappush 동작이 수행된다.

즉, 이때 heapify가 진행된다

 

 

✅  결론 1. put 쓰자 (써도 heapify 잘 된다)

put 쓰자

put 메소드(Queue)에서 _put 메소드(PriorityQueue) call

 

 

✅  결론 2. (내부구현) heappush, heappop을 호출한다

PriorityQueue 클래스 메소드를 살펴보자.

from heapq import heappush, heappop


class PriorityQueue(Queue):
	# ... (중략)
    def _put(self, item):
        heappush(self.queue, item)

    def _get(self):
        return heappop(self.queue)

 

굳이 Queue의 put을 거치는 이유?

Queue의 put이 thread-safe 하다.

 

Queue에서는 init 시, 이런 mutex lock을 정의한다.

self.not_full = threading.Condition(self.mutex)

 

그리고 Queue의 put 메소드는, 

lock을 얻은 상태에서만 실행된다.

  def put(self, item, block=True, timeout=None):
        with self.not_full:
            if self.maxsize > 0:
            	'''생략'''

 

즉, thread-safe하기 때문에 Queue의 put을 거치는 것이다.

 

 

✅ 사용 예시

from queue import PriorityQueue

pq = PriorityQueue()

# 원소 추가
pq.put(2)
pq.put(1)
pq.put(3)


# 원소 삭제
pq.get() # 1
pq.get() # 2
pq.get() # 3
pq.get() # 무한 반복에 걸림 (주의)
pq._get() # 무한 반복에 걸리진 않지만, 권장 x (private method)

 

---

⭐️ 3. heapq

- 파이썬의 우선순위 큐 구현체 (모듈)

- 이진 트리 형태

- 최소 힙

    - 부모 노드 값 <= 자식 노드의 값

 

 

✅ heapq생성

import heapq

heap = []
# heapq 메소드의 인자로 heap list 넘김

 

위에서 본 PriorityQueue와 달리, 

리스트를 heap처럼 다룬다.

 

heapq의 method의 인자로 리스트를 넘기는 방식으로 사용된다.

 

 

그럼 heapq의 method를 보자!

 

 

✅ 주요 메소드 (heapq)

def heappush(heap, item):
    heap.append(item)
    _siftdown(heap, 0, len(heap)-1)

def heappop(heap):
    lastelt = heap.pop() # 맨 마지막 원소 pop
    
    if heap:
        # 리스트가 비어 있지 않다면 수행
        returnitem = heap[0]
        # 힙 구조 유지
        heap[0] = lastelt
        _siftup(heap, 0)
        return returnitem
                
    # 리스트가 비어 있다면 리스트의 마지막 원소 반환
    return lastelt

def heapify(x):
    # list를 heap으로 전환.
    
    n = len(x)
    for i in reversed(range(n//2)):
        _siftup(x, i)

- 원소 추가: heappush()

- 원소 삭제: heappop()

- 힙 구조 유지(list -> heap): heapify()

 

주의:

원소 추가, 삭제 후 heapify 함수 부를 필요 X

list를 heap으로 변경하기 위해 heapify 함수를 부름

 

+ heappush, heappop 함수의 인자로 사용되는 list는 

heapify가 되었다 가정.

 

 

✅ 사용 예시

import heapq

# 힙 생성
heap = []

# 원소 추가
heapq.heappush(heap, 2)
heapq.heappush(heap, 1)

# 원소 삭제 (가장 작은 원소)
item = heapq.heappop(heap) # 1

# 가장 작은 원소 출력 (원소 삭제 X)
item = heap[0]

# list를 heap으로 변형
listA = [3, 1, 6]
heapq.heappush(listA, 2) # listA는 heapify가 되었다 가정하므로 정상동작 x # 3, 1, 6, 2
heapq.heapify(listA) # listA 리스트 heapify

 

---

⭐️ 4. PriorityQueue VS heapq 한 줄 정리

PriorityQueue VS heapq 비교

위에서도 다루어 보았듯,

PriorityQueue는 thread-safe 하다는 점에 차이가 있다.

 

---

⭐️ 5.기본 (min 순서대로) 사용하기

 

✅ PriorityQueue

from queue import PriorityQueue

pq = PriorityQueue()

# 원소 추가
pq.put(2)
pq.put(1)
pq.put(3)


# 원소 삭제
pq.get() # 1
pq.get() # 2
pq.get() # 3

 

✅ heapq

import heapq

# 힙 생성
heap = []

# 원소 추가
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)

# 원소 삭제 (가장 작은 원소)
item = heapq.heappop(heap) # 1

---

⭐️ 6. 역순 (max 순서대로) 사용하기

 

✅ PriorityQueue

from queue import PriorityQueue

pq = PriorityQueue()

# heap으로 생성할 원소들
items = [3, 1, 2]

for item in items:
	pq.put(-item) # 음수로 입력

# pq: [-3, -2, -1]

# 원소 삭제 (가장 큰 원소)
for _ in range(len(heap)):
	print(-pq.get()) # 3, 2, 1

 

✅ Heapq

import heapq

# 힙 생성
items = [3, 1, 2] # heap으로 생성할 원소들
heap = []

# 원소 추가
for item in items:
	heapq.heappush(heap, -item) # 음수로 입력
    
# heapq: [-3, -2, -1]

# 원소 삭제 (가장 큰 원소)
for _ in range(len(heap)):
	print(-heapq.heappop(heap)) # 3, 2, 1

---

⭐️ 7. 코딩 테스트에서는 heapq를 쓰자

heapq가 PriorityQueue보다 속도가 더 빠르다.

 

위에서도 다루어 보았듯,

PriorityQueue는 thread-safe 하기 때문이다. 

 

---

참고 자료

 

우선순위 큐 성능 시험에 관한 연구

python3.9 heapq.py 라이브러리

python3.9 queue.py 라이브러리

https://2jinishappy.tistory.com/102

자료구조 Heap(힙)이란? 기본 연산과 HeapSort, Heapify에 대해

https://dawitblog.tistory.com/160

[자료구조]우선순위 큐(Priority Queue)