1. 스택/큐/우선순위 큐
- stack : 데이터의 정렬 순서가 기준, 후입선출
- queue : 데이터의 정렬 순서가 기준, 선입선출
- priority queue : 데이터 우선순위(크기, 비중) 기준, min/max heap 자료구조 활용
2. 우선순위 큐
- 리스트에 넣어 선형탐색 및 조건확인 후 추출할 수 있지만, heap(max/min heap) 자료구조를 활용하여 구현하는 것이 시간복잡도 면에서 훨씬 유리하다.
- 리스트 : input/O(1) -> output/O(N)
- heap 활용 : input/O(logN) -> output/O(logN)
3. heap 자료구조
힙 자체는 완전이진트리의 일종, 힙은 항상 루트노드를 제거한다.
heap을 구성하는 과정을 heapify라고 하고, 현재 구성되어 있는 형태(최소/최대힙)에 따라 상향식 혹은 하향식으로 원소를 삽입한다(logN).
