[자료구조] 우선순위 큐 (heapq)

우선순위 큐

• 우선순위 큐(Priority Queue)란 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 큐이다. 데이터를 우선순위에 따라 처리하고 싶을 때 유용한 자료구조이다.
• 힙 자료구조는 우선순위 큐를 구현하기 위해 사용되는 자료구조이다.

대부분의 언어에서 표준 라이브러리 형태로 지원한다. 파이썬에는 PriorityQueue 또는 heapq를 사용할 수 있는데, 일반적으로 heapq가 더 빠르게 동작하기 때문에 수행 시간이 제한된 경우에는 heapq 사용을 권장한다.

 

• 큰 숫자에 우선순위를 부여하는 힙을 최대 힙(Max Heap), 작은 숫자에 우선순위를 부여하는 힙을 최소 힙(Min Heap)이라고 한다.
• heapq는 내부적으로 트리로 구현되어 있어 데이터를 삽입, 삭제하는데 O(logN) 만큼의 시간이 소요된다.

 

heapq 사용하기

heapq를 임포트한 후에, 우선순위 큐로 사용할 리스트를 하나 선언한다.

데이터 삽입은 heapq.heappush(삽입될 리스트, 삽입할 값)

데이터 삭제는 heapq.heappop(삭제될 리스트)

이렇게 사용할 수 있다.

 

최소 힙을 사용한 오름차순 정렬

이러한 heapq의 특성을 사용해 정렬 알고리즘을 구현할 수 있다.

import heapq

# heapq를 사용한 정렬
def heapsort_asc(nums):
    h = []
    res = []

    for num in nums:
        heapq.heappush(h, num)
    
    for i in range(len(h)):
        res.append(heapq.heappop(h))
    
    return res


nums = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
res = heapsort_asc(nums)
print('res:', res)

 

최대 힙을 사용한 내림차순 정렬

파이썬 heapq 라이브러리에서는 최대 힙을 지원하지 않기 때문에 힙에 값을 삽입, 삭제할 때 음수 부호(-)를 붙여 최대 힙을 구현한다.

def heapsort_desc(nums):
    h = []
    res = []

    for num in nums:
        heapq.heappush(h, -num)
    
    for i in range(len(h)):
        res.append(-heapq.heappop(h))
    
    return res


nums = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
res = heapsort_desc(nums)
print('res:', res)