[자료구조 및 알고리즘] 우선순위 큐 (Priority Queue)

우선순위 큐

 

우선순위 큐는 데이터를 추가한 순서대로 삭제하는 큐와 달리, 데이터 추가는 어떤 순서로 해도 상관 없지만 데이터를 제거할 때는 가장 작은 값을 제거하는 특성을 가지는 자료구조이다. 이는 내부적으로 정렬 메커니즘이 있다는 것을 의미한다.

 

 우선순위 큐는 내부적으로 힙이라는 완전 이진 트리로 되어있다. 힙 트리의 루트노드에는 데이터들 중에 가장 큰 값 혹은 가장 작은 값을 담게 되는데 전자는 최대힙(Max-heap) 후자는 최소힙 (Min-heap)이라고 한다. 어떤 값을 넣어도 항상 루트에 가장 큰 값 또는 가장 작은 값이 위치하도록 자동으로 갱신한다. 이 과정이 꽤 효율적이라 우선순위 큐의 값 삽입/삭제 시간 복잡도는 O(logN)이다. 무작위 숫자들을 힙에 전부 넣고 하나를 빼면 정렬된 결과를 얻을 수 있는데 이를 힙정렬이라고 한다. PriorityQueue 모듈은 멀티스레딩 환경까지 고려해서 스레드 간에 안전한 방식으로 동작하는 모듈이기 때문에 느리다. 멀티스레딩 환경을 고려하지 않는 대신 더 빠른 모듈은 heapq이다.

 

 

코드

from queue import priorityQueue

pq = priorityQueue() #priorityQueue() 생성자를 이용해 우선순위 큐를 초기화할 수 있다

pq.put(1) # 우선순위 큐에 원소 추가: put() 메서드를 이용한다.
pq.put(3)
pq.put(2)

pq.get() # 1 # 우선순위 큐에 원소 삭제: get() 메서드를 이용한다. 이때 작은 값부터 삭제된다.
pq.get() # 2
pq.get() # 3

우선순위 큐의 디폴트 사이즈는 무한대이다. 크기를 정하고 싶으면 maxsize = x 를 넘겨주면 된다.

 

import heapq

h = []
heapq.heappush(h,123)
heapq.heappush(h,789)
heapq.heappush(h,456)

 

heapq는 파이썬에서 우선순위 큐를 만들 때 사용한다. priorityQueue 모듈은 멀티 스레딩 환경까지 고려해서 스레드간에 안전한 방식으로 동작하는 모듈이라 속도가 느리다는 특징이 있다. 그래서 멀티 스레딩 환경을 고려하지 않아도 될 때는 heapq 모듈을 사용하기도 한다. 파이썬에서 heapq는 최소 힙을 구성한다.