[Python] heapq에 대해서 :: 힙 큐 알고리즘, 우선순위 큐 알고리즘

먼저 큐(queue)란?
FIFO 구조로 이루어진 자료구조. 가장 먼저 들어온 값이 가장 먼저 나간다.

리스트로도 구현할 수 있지만 실행 시간 단축을 고려하여
일반적으로 `collections` 라이브러리에서 양방향 큐 `deque`를 불러와서 구현한다.

우선순위 큐란?
말 그대로 큐에서 데이터를 pop할 때 FIFO 순서가 아닌 우선순위를 기준으로 빼내는 자료구조.
즉, 제일 앞의 값이 우선순위가 높으면 빼내고 낮으면 다시 맨 뒤로 보낸다.

힙(heap)이란?
힙이라고 하면 가장 먼저 떠오르는 건 힙 트리 자료구조.
최소 힙/최대 힙 기반 이진트리로, 값을 삽입하거나 삭제할 때 순서대로 정렬하여 저장한다.

즉, 부모 노드의 값이 항상 자식노드보다 작으면서 루트 노드의 값이 가장 작은 최솟값으로 유지되는 구조!
(최소 힙 기준)

그렇다면 힙 큐(heapq)란?
힙 트리를 기반으로 한 우선순위 큐!
값을 삽입할 때 정렬이 되며, `heap[0]`값이 최솟값으로 설정되어 pop 연산을 할 경우 항상 최솟값이 반환된다.
매순간 데이터 정렬을 필요로 하는 문제에 사용하면 실행 시간을 단축시킬 수 있는 자료구조.

from heapq import heappush, heappop, heappushpop, heapify

heap = []

heappush(heap, item)
# heap에 item 값을 정렬하여 삽입

heappop(heap)
# heap[0]을 삭제하고 반환
# 힙이 비어 있으면 IndexError가 발생하기 때문에 처리 필요

heappushpop(heap, item)
# 힙에 item을 삽입한 다음, heap[0]을 삭제하고 반환
# heappush()한 다음 heappop()을 별도로 호출하는 것보다 더 효율적임!

heapify(x)
# 리스트 x를 제자리에서 힙으로 변환 (힙 규칙에 맞게 정렬)

* heapq는 기본적으로 최소 힙을 지원하기 때문에 최대 힙을 구현하고 싶다면 숫자 데이터의 부호를 `-`로 바꿔서 최소 힙으로 `heappush`한 후, 나중에 최솟값부터 `heappop`을 해줄 때 다시 부호를 `+`로 바꿔서 꺼내주면 최대 힙의 결과와 동일한 값을 얻을 수 있다. 

heapq — Heap queue algorithm