[Python] 우선순위 큐

개요

데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬의 PriorityQueue(우선순위 큐)에 대해서 알아본다.

정의

우선순위 큐는 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조이다.

사용법

1. 원소 넣기

import heapq
# 우선순위 큐를 구현하기 위한 heapq import
h = []
heapq.heappush(h, (1,"Lotte Giants"))
heapq.heappush(h, (2,"NC Dinos"))
heapq.heappush(h, (10,"Doosan Bears"))
heapq.heappush(h, (7,"Hanhwa Eagles"))
heapq.heappush(h, (4,"KT Wiz"))
print(h)

위와 같이 작성하면 아래와 같이 배열로 구현된 힙을 보여준다.

[(1, 'Lotte Giants'), (2, 'NC Dinos'), (10, 'Doosan Bears'), (7, 'Hanhwa Eagles'), (4, 'KT Wiz')]

2. 원소 꺼내기

원소를 꺼내기 위해서는 heapq.heappop을 활용하면 된다.

first = heapq.heappop(h)
second = heapq.heappop(h)
third = heapq.heappop(h)

print(first)
print(second)
print(third)
print(h)

위와 같이 작성하면 다음과 같은 결과가 나온다.

(1, 'Lotte Giants')
(2, 'NC Dinos')
(4, 'KT Wiz')
[(7, 'Hanhwa Eagles'), (10, 'Doosan Bears')]

3. 배열로 부터 힙 정렬 만들기

1번의 방법으로 배열을 힙으로 만들면 시간 복잡도는 O(nlogn)이다. 그러나 배열로부터 힙을 만드는 최적의 알고리즘의 시간 복잡도는 O(n)으로 알려져 있다. 파이썬에서는 O(n)의 시간으로 배열을 힙으로 만들 수 있는 heapq.heapfy 함수를 제공한다.

주의할 점은 배열 자체가 힙으로 바뀐다는 점이다.

import heapq

h = [(1, 'Lotte Giants'), (2, 'NC Dinos'), (10, 'Doosan Bears'), (7, 'Hanhwa Eagles'), (4, 'KT Wiz')]

heapq.heapify(h)
print(h)

결과는 1번의 결과와 같다.

최대 힙 (max-heap)

하지만 heapq는 기본적으로 최소 힙 밖에 지원을 안한다. 따라서 다음과 같이 키 값을 변환해서 넣어준다.

import heapq

h = [(1, 'Lotte Giants'), (2, 'NC Dinos'), (10, 'Doosan Bears'), (7, 'Hanhwa Eagles'), (4, 'KT Wiz')]
max_h = [(-ele[0], ele[1]) for ele in h]
heapq.heapify(max_h)
print(max_h)

결과는 다음과 같다.

[(-10, 'Doosan Bears'), (-7, 'Hanhwa Eagles'), (-1, 'Lotte Giants'), (-2, 'NC Dinos'), (-4, 'KT Wiz')]