파이썬 heapq

파이썬에서는 힙(heap) 기능을 위해 heapq 라이브러리를 제공한다.

간단하게 heap이란 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 

보통 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

힙은 최대 힙, 최소 힙이 있으며 파이썬에서는 힙을 보통 배열로 사용하기 때문에 최대 힙은 내림차순, 최소 힙은 오름차순이라고 이해해도 될 것 같다. heapq는 기본적으로 최소 힙만을 지원하기 때문에 최대 힙을 사용하고자 한다면 -부호를 붙여야 한다.

import heapq


def heapsortASC(iterable):
    h = []
    result = []

    for value in iterable:
        heapq.heappush(h, value)

    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result


def heapsortDESC(iterable):
    h = []
    result = []

    for value in iterable:
        heapq.heappush(h, -value)

    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result


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

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


// 결과
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
// [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]