큐(queue) : 선입선출(FIFO). 가장 먼저 삽입된 데이터가 가장 먼저 추출됨
우선순위 큐(Priority Queue)
- 각 원소들이 우선순위를 가지는 큐
- 같은 우선순위를 가진다면, 먼저 들어온 원소를 먼저 처리
- 힙(heap)으로 구현
pop,push
힙(Heap)
- 데이터에서 최대값과 최소값을 가장 빠르게 찾을 수 있도록 만들어진 완전 이진 트리
- Max Heap : 부모 노드의 값이 항상 자식 노드들의 값보다 큼
- Min Heap : 부모 노드의 값이 항상 자식 노드들의 값보다 작음
파이썬 Heapq 라이브러리
- 기본적으로 최소 힙(Min heap) 구조
- 모든 원소의 부호를 반대로 바꿔주면 max heap과 비슷하게 사용 가능. (+, - 연산 반대로 적용!)
import heapq
heapify
- 리스트 arr를 heap으로 변환
import heapq
arr = [1,4,2,3]
print(arr) # [1,4,2,3]
heapq.heapify(arr)
print(arr) # [1,3,2,4]push
heap.heappush(heap, item)- 힙의 형태를 유지하며 item을 push
heapq.heappush(hq,2) # 힙 원소 추가
heapq.heappush(hq,7)
heapq.heappush(hq,3)pop
heap.heappop(heap)- 힙의 형태를 유지하며 가장 작은 항목을 pop
- 비어있으면 인덱스 에러
- 반환하지 않고 접근하고 싶다면
heap[0]활용
heapq.heappop(hq) # 2참고
https://velog.io/@mein-figur/Python%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-heapq
https://greenring.tistory.com/36
