[Python] priority queue 우선순위 큐

▶ priority queue우선순위 큐 

 

사용자의 우선순위가 높은 값 먼저 출력한다. 

O(logN)의 속도로 자료를 넣었다 뺐다 할 수 있다. 

처음에 시간복잡도를 계산할 때 

O(n^2)이 안될 것 같다 하면 쓰기 

 

우선순위 큐의의 내부 원리는 힙이라는 자료구조로 되어있다. 

모듈, 클래스 다 힙으로 구성되어 있음

 

파이썬에서는 priority que를 사용하면

완벽한 이진트리의 형태를 유지한다

로그 n의 속도로 자료를 저장하고 빼온다

​

파이썬에서는 import heapq를 사용한다

다른 책에서는 from queue import PriorityQueue라고 하긴 하는데

ps분야 problem solving 분야 즉 알고리즘 문제에서는

두번째는 시간 복잡도가 느려서 사용 안한다

 

heapq.heappush(arr,4)

이렇게 arr 내부에 있는 자료구조를 힙의 자료구조로 만들 수 있따

파이썬에서는 heapq를 사용하면 min heap이 디폴트 값이다

파이썬에서는 무조건 오름차순이다

​

heapq.heappush 매소드를 사용해서 arr에 값을 추가하면서 heap의 자료구조로 바꾼다.

맨 앞에 루트 노드만 의미가 있따

우선순위가 가장 높은 것만 의미가 있고 나머지는 의미가 없음

​