Heap 자료구조 (priority_queue), set, map(dictionary)

1. Heap 자료구조

데이터의 우선순위에 대한 개념을 도입하기 위해 만들어진 자료구조입니다.

Max Heap, Min Heap 등이 있으며, 각각 최댓값, 최솟값을 항상 빠르게 찾아낼 수 있습니다.

Heap 자료구조가 처음인 분들은 한번씩 구현해보는 것도 추천드립니다.

2. 우선 순위 큐 (Priority Queue)

데이터에 우선순위를 매긴 후, 어느 데이터를 언제 집어넣어도 우선순위가 가장 높은 데이터부터 차례대로 나오는 큐입니다.

Heap 자료구조로 구현이 되어있으며, 삽입과 삭제 모두 $O(logN)$입니다.

Heap의 모양이 큐와 유사해서 우선 순위 큐라는 이름이 붙었습니다.