Dev On The Coffee Dev On The Coffee

# 우선순위 큐 (Priority Queue) 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 우선순위 큐는 리스트(List), 힙(Heap) 두가지 방식으로 구현 가능하다. 리스트의 경우 데이터를 단순히 리스트의 뒤에 삽입하고 우선순위를 기준으로 선형탐색한다. 따라서 삽입시간은 시간복잡도가 O(1)이지만, 삭제시간은 선형탐색으로 인해 O(N)이 소요된다. 반면, 힙은 삽입시간, 삭제시간 모두 O(logN)의 시간복잡도를 보장한다. 힙의 또다른 특징은 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업만으로도 정렬이 수행된다는 점이다. 이를 힙 정렬(Heap Sort)이라 하는데, 힙 정렬은 O(NlogN)의 시간 복..