우선순위 큐란?

우선순위를 가진 항목들을 저장하는 큐
FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다.

우선순위 큐는 2가지로 구분된다.

• 최소 우선순위 큐 : 가장 우선순위가 낮은 요소부터 삭제
• 최대 우선순위큐 : 가장 우선순위가 높은 요소부터 삭제

우선순위 큐 구현 방법

• 배열을 이용한 우선순위 큐
• 연결리스트를 이용한 우선순위 큐
• 힙(heap)을 이용한 우선순위 큐

여기에선 힙을 이용한 우선순위 큐를 설명한다.
힙을 이용한 우선순위 큐 시간 복잡도는 O(logn)이다.

힙(heap)란?

key(부모노드) >= key(자식노드) 또는 key(부모노드) <= key(자식노드) 를 만족하는 완전 이진 트리이다.

힙 종류

• 최대 힙 : key(부모노드) >= key(자식노드) 완전 이진트리
• 최소 힙 : key(부모노드) <= key(자식노드) 완전 이진트리

Heapq

python의 heapq 라이브러리로 쉽게 최소힙과 최대힙을 구현할 수 있다.

heapq는 기본적으로 최소힙으로 설정되어 있다.

• 모든 k에 대해 heap[k] <= heap[2*k+1] 또는 heap[k] <= heap[2*k+2] 만족
• 가장 작은 요소가 heap[0]에 위치

heappush - 값 추가

heapq.heappush(heap,item)

import heapq

pq = []

heapq.heappush(pq, 3)
heapq.heappush(pq, 10)
heapq.heappush(pq, 1)
heapq.heappush(pq, 0)
heapq.heappush(pq, 4)

print(pq)
# [0, 1, 3, 10, 4]

순서는 다음과 같이 된다!

heappop - 값 삭제

heapq.heappop(heap)

위의 상황에서

print(heapq.heappop(pq))
# 0

힙의 형태를 유지하면서 가장 작은 항목을 pop을 하여 다음과 같이 된다.