heapq
-
우선순위 큐언어/파이썬 2021. 1. 21. 17:55
우선순위 큐는 큐 또는 스택과 같은 추상 자료형과 유사하지만 추가로 각 요소의 '우선순위'와 연관되어 있다. 스택은 가장 나중에 삽입된 요소를 먼저 추출(LIFO), 큐는 가장 먼저 삽입된 요소를 먼저 추출(FIFO) 한다. 그러나 이와 달리 우선 순위 큐는 어떠한 특정 조건에따라 우선순위가 가장 높은 요소가 추출되는 자료형이다. 대표적으로 최댓값 추출을 들 수 있는데, 예를 들어 큐에 [1, 4, 5, 3, 2,] 가 들어 있고 최댓값을 추출하는 우선순위 큐가 있다고 가정하자 이 경우 항상 남아 있는 요소들의 최댓값이 우선순위에 따라 5, 4, 3, 2, 1 순으로 추출 된다. 이는 정렬 알고리즘을 사용하면 우선순위 큐를 만들 수있다는 의미이기도 하다. n개의 요소를 결정하는데 S(n)의 시간이 소요된..