자료구조 & 알고리즘/자료구조
자료구조 우선순위 큐(Priority Queue)와 힙(heap)
먼저 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 스택(Stack) 자료구조에서 추출되는 데이터는 가장 나중에 삽입된 데이터이고 큐(Queue) 자료구조에서 추출되는 데이터는 가장 먼저 삽입된 데이터, 우선순위 큐(Priority Queue) 에서는 가장 우선순위가 높은 데이터가 추출이 된다. 우선순위 큐(Priority Queue)를 구현하는 방법에는 단순 리스트를 이용하여 구현하는 방법 힙(heap)을 이용하여 구현하는 방법이 있다. 데이터의 개수가 N개 일때, 구현 방식에 따라서 시간 복잡도를 비교한 내용은 아래와 같다. 단순 리스트를 이용하면 삽입에는 O(1), 삭제에는 O(N) 의 시간 복잡도를..
