🗒️ 우선순위 큐
- 큐는 먼저 들어온 데이터가 먼저 처리되는 자료구조이지만, 우선 순위 큐는 우선 순위가 높은 데이터부터 처리하는 자료구조이다.
배열, 연결리스트, 힙으로 모두 구현할 수 있지만 보통 시간복잡도가 적은 힙을 사용한다.
💡 우선순위큐
from queue import PriorityQueue
q = PriorityQueue()
# 삽입
q.put(3)
q.put(2)
q.put(1)
# 삽입시 우선순위 지정
q.put((5,"banana"))
q.put((1,"apple"))
q.put((3,"FINE"))
# 반환
print(q.get()) # 1
print(q.get()) # 2
print(q.get()) # 3
# 사이즈
print(q.qsize())
# 튜플 값만
print(q.get()[1]) # apple
🗒️ 힙(heap)
- heap은 쌓아 놓음, 쌓아 놓은 더미라는 뜻이다. 기본적인 정의는 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진트리이다. 반대로 '부모의 값이 자식의 값보다 항상 작다' 도 힙이 될 수 있다.
- 최솟값, 최댓값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리의 자료구조이다. 힙은 최대 힙과 ,최소 힙으로 나타 낼 수 있다.
💡 힙 구현
import heapq
q = []
heapq.heappush(q,3)
heapq.headpush(q,2)
heapq.headpush(q,1)
heapq.headpop(q) # 1
heapq.headpop(q) # 2
heapq.headpop(q) # 3
루트를 삭제하고 힙을 재구성 하는 모습
