우선순위 큐 개념 정리(리스트 우선순위큐, 힙 우선순위큐 / 시간복잡도 / 파이썬 구현)

우선순위 큐 특징 : 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 예시) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야하는 경우 구현 방법 1) 단순히 리스트를 이용하여 구현한다. 2) 힙(heap)을 이용하여 구현한다. 시간복잡도 - 데이터의 개수가 N개 일 때, 구현 방식에 따라서 시간 복잡도를 비교한 내용은 다음과 같다. 1) 리스트 - 삽입 시간 : O(1) (리스트의 가장 뒤에 추가가 되기에 O(1)이 소요됨) - 삭제 시간 : O(N) (모든 데이터를 확인하기 때문에 선형 시간 복잡도를 가짐) 2) 힙 - 삽입 시간 : O(logN) - 삭제 시간 : O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. (힙정..

2021.06.18