우선순위 큐, heap 큐

우선순위 큐란?

• 각 원소들에 순위를 부여하고 그 순위에 맞게 정렬하는 자료구조
• push, pop 함수를 지원한다.

PriorityQueue

from queue import PriorityQueue
q = PriorityQueue()  # 우선순위 큐 선언

q.put(5)  # PriorityQueue의 경우 push로 put 메서드를 사용
q.put(4)
q.put(3)
# q.put('a')  비교할 수 없는 type의 원소가 put되면 TypeError

q.pop()  # 3
q.pop()  # 4
q.pop()  # 5

이처럼 값이 작을수록 우선순위가 된다.

q.put((1, 'c'))
q.put((2, 'b'))
q.put((3, 'a'))

q.pop()  # (1, 'c')
q.pop()  # (2, 'b')
q.pop()  # (3, 'a')

이처럼 tuple이나 list 형태로도 큐에 put 할 수 있으며, 이 때 우선순위는 첫 번째 값으로 부여한다.

Heapq

import heapq

hq = [4,3,2,1]
heapq.heapify(hq)

print(hq)  #  [1, 3, 2, 4]
print(heapq.heappop(hq))  # 1
print(heapq.heappop(hq))  # 2
print(heapq.heappop(hq))  # 3
print(heapq.heappop(hq))  # 4

• heapq는 default로 최소 힙 형태이며, 최소 힙은 루트 노드가 가장 작은 값을 갖는 힙이다.
• heapq를 print하면 값으로 정렬이 되어있는 것은 아니지만, heappop의 경우 가장 작은 값부터 차례대로 pop하는 것을 볼 수 있다.
• PriorityQueue와 마찬가지로 tuple, list와 같은 형태의 데이터도 다룰 수 있다.