[자료구조] 우선순위 큐

우선순위 큐는 내부적으로 힙(heap)이라는 완전이진트리 Complete binary Tree로 되어 있다. 힙 트리의 루트 노드(root node)에는 데이터들 중에 가장 큰 값 혹은 가장 작은 값을 담게 되는데, 전자는 최대힙(max-heap), 후자는 최소힙(min-heap)이라 한다. 어떤 값을 넣어도 항상 루트에 가장 큰 값 또는 가장 작은 값이 위치하도록 자동으로 갱신한다. 이 과정이 꽤 효율적이라 우선순위 큐의 값 삽입/삭제 시간 복잡도는 O(log N)이다. 무작위 숫자들을 힙에 전부 넣고 하나씩 빼면 정렬된 결과를 얻을 수 있는데, 이게 힙정렬이다.

from queue import PriorityQueue

pq = PriorityQueue()
pq.put(123)
pq.put(789)
pq.put(456)
while not pq.empty():
	print(pq.get())

멀티스레딩 환경을 고려하지 않는 대신 더 빠른 모듈은 heapq이다. 알고리즘 문제는 이 heapq를 사용하자. 리스트를 하나 만들고 그 안에 데이터를 저장하는 방식이다.

import heapq

h = []
heapq.heappush(h, 123)
heapq.heappush(h, 789)
heapq.heappush(h, 456)
while len(h):
	print(heapq.heappop(h))