[알고리즘] 우선순위 큐(Priority Queue)와 힙(Heap)

우선순위 큐(Priority Queue)란?

우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다. 데이터 추가는 어떤 순서로 해도 상관 없지만, 제거될 때는 가장 작은 값을 제거하는 특징을 가진 자료구조이다. Python에서는 이런 로직이 내부적으로 구현되어 있는 heapq 모듈을 제공한다.

힙(Heap) 자료구조란?

heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(Min heap) 자료구조를 제공한다. 부모노드와 서브트리간 대소 관계가 성립한다. 즉, 반 정렬된 상태를 유지하며 항상 루트 노드에 최솟값이 들어가게 된다. 그렇다고 힙(Heap)이 완벽하게 정렬된 것은 아니다. 부모 자식 간의 대소 관계만 명확할 뿐이다.

cf) 최소 힙(Min heap)이란?

부모 노드의 값이 자식 노드보다 크거나 같은 완전이진트리이다.

이미지 출처 - https://suyeon96.tistory.com/31

💡Python의 heapq 모듈

• 최소 힙(Min Heap)의 구조
• 모든 k에 대해 heap[k] <= heap[2*k+1]와 heap[k] <= heap[2*k+2]를 만족
• 가장 작은 원소가 heap[0]에 위치한다.
• heap을 만들기 위해서는, lst = [](초기화된 리스트)를 heap.heappush(lst, 숫자) 이렇게 heappush 함수의 매개변수로 사용하거나, heapify를 통해 값이 들어있는 리스트를 힙으로 변환 가능

💡우선순위 큐의 시간복잡도

이미지 출처 - https://suyeon96.tistory.com/31

cf) 스택(Stack), 큐(Queue)의 시간복잡도

삽입과 삭제는 O(1)의 시간복잡도를 가지고, 검색은 O(n)의 시간복잡도를 가진다.

heapq 활용 예시 코드

import heapq # 우선순위 큐를 사용하기 위한 모듈

# 초기화 배열을 heappush하면 heap의 자료형으로 바꾼다. 
# (heapify가 저절로 된다고 생각하면 됨)
arr = [] 

heapq.heappush(arr, 4)  
heapq.heappush(arr, 15)
heapq.heappush(arr, 2)
heapq.heappush(arr, 7)
heapq.heappush(arr, 5)
heapq.heappush(arr, 9)

print(heapq.heappop(arr)) # logN의 속도로 우선순위가 가장 높은 값을 출력

# 최솟값부터 출력이 되도록 코드 적어보기
arr2 = [9,7,6,7,5,26,47,62,5,1]
tmp = arr2[:]
heapq.heapify(tmp)

for _ in range(N):
    print(heapq.heappop(tmp), end=' ') # 최솟값부터 pop

# 최솟값을 삭제하지 않고 읽기만 하고 싶을 땐
# heap[0]으로 접근

Max heap 만들기

# max heap
arr3 = [8,7,64,9,12,5,7,56]

heap = []

for i in range(len(arr3)):
    heapq.heappush(heap, -arr3[i]) # 음수로 만들어서 heap에 push
for i in range(len(arr3)):
    print(heapq.heappop(heap)*-1)  # heappop은 원소를 삭제하면서 그 원소를 return 

# 람다 이용
rev = lambda x: x*-1
heap1 = list(map(rev,arr3))
heapq.heapify(heap1)               # 이미 값이 들어있기 때문에 heapify 필요
for i in range(len(arr3)):
    print(-heapq.heappop(heap1))

# 튜플
for i in range(len(arr3)):
    heapq.heappush(heap, (-arr3[i], arr3[i])) # (원본, -원본)을 heapq에 push
for i in range(len(arr3)):
    print(heapq.heappop(heap)[1])

nsmallest(), nlargest() 함수 사용

• nsmallest(n, lst): n개의 작은 수를 오름차순으로 담은 리스트를 반환
• nlargest(n, lst): n개의 큰 수를 내림차순으로 담은 리스트를 반환

# 함수를 import
from heapq import nsmallest, nlargest

tmp = nsmallest(3, [4, 1, 7, 3, 8, 5])[:]
print(tmp) # [1, 3, 4]
print(tmp[-1]) # 원본 배열에서 n번째로 작은 수를 출력

tmp2 = nlargest(3, [4, 1, 7, 3, 8, 5])[:]
print(tmp2) # [8, 7, 5]
print(tmp[-1]) # 원본 배열에서 n번째로 큰 수를 출력

Python의 PriorityQueue 모듈

파이썬에는 우선순위 큐의 활용을 위해 PriorityQueue라는 모듈을 추가로 제공하고 있다. 소스 코드를 보면 PriorityQueue 클래스가 heapq 모듈을 이용하고 있는 것을 알 수 있다.

둘의 차이는 Thread-Safe 하느냐 Non-Safe 하느냐에 있다. Thread-Safe를 요구하는 상황이면 PriorityQueue를 사용하고, Thread-Non-Safe해도 되는 상황이면 heapq를 쓰는 것이 시간적 측면에서 효율이 좋다.

🎈우선순위 큐 활용 문제

• 백준
  • 가운데를 말해요
  • 카드 정렬하기