[python] - 우선순위 큐, 힙

🗒️ 우선순위 큐

- 큐는 먼저 들어온 데이터가 먼저 처리되는 자료구조이지만, 우선 순위 큐는 우선 순위가 높은 데이터부터 처리하는 자료구조이다. 
배열, 연결리스트, 힙으로 모두 구현할 수 있지만 보통 시간복잡도가 적은 힙을 사용한다.

💡 우선순위큐

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

---

루트를 삭제하고 힙을 재구성 하는 모습