[파이썬] 우선순위 큐(Priority Queue), 힙(Heap)

우선순위 큐(Priority Queue) 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조 데이터를 우선순위에 따라 처리하고 싶을 때 사용 어떤 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우에 사용을 한다. 자료구조 추출되는 데이터 스택 가장 나중에 삽입된 데이터 (불공평하다) 큐 가장 먼저 삽입된 데이터 (공평하다) 우선순위 큐 가장 우선순위가 높은 데이터 구현하는 방법에는 두 가지 방법이 있다. 1. 리스트를 이용 2. 힙을 이용 우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙 O(logN) O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. 이것을 힙 정렬이라고 부른다. 이 경우 시간 복잡도는 O(..

→2021.01.07