heapq 라이브러리

우선순위 큐를 만들기 위해서 사용하는 자료구조는 heapq 이다. 우선순위 큐란 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 이다. 예로 들어서 비용이 가장 높은 물건을 우선적으로 추출하고 싶다면 우선순위 큐를 사용하면 된다.

이러한 우선순위 큐는 heapq 라이브러리를 통해서 구현되어 있다. 우선순위 큐는 최소 힙이나 최대 힙으로 이용할 수 있다. 이때 최소 힙은 부모 노드가 자식노드보다 크기가 작은 자료구조로서 트리 자료구조에 속한다.

• 데이터를 삽입하거나 삭제하는데 log(n) 이 걸린다. (리스트에 비해서 월등히 빠르다.)
• 데이터를 꺼낼 때 가장 높은 값이나 혹은 가장 낮은 값을 보장한다. (파이썬의 heapq 라이브러리는 가장 낮은 값을 기준으로 한다)

# 사용예시
import heapq

def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for _ in range(len(h)):
        result.append(heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

• 힙에 데이터를 삽입할 때는 heappush, 데이터를 추출할 때는 heappop 메서드를 사용한다.

최소값부터 출력하는 것이 아닌 최대값 부터 출력을 하고 싶으면 아래와 같이 코드를 작성하면 된다.

import heapq

def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기 (음수로 저장되어 있으므로 - 곱해서 반호나)
    for _ in range(len(h)):
        result.append(-heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result) # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

• 단순히 숫자에 음수를 취하면 최대값부터 차례대로 나오게 된다.