우선순위 큐(with Python)

[heapq]

파이썬에서는 힙(heap)기능을 위해 heapq 라이브러리를 제공한다. heapq는 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용된다. heapq 외에도 PriorityQueue 라이브러리를 사용할 수 있다. 하지만 코딩 테스트 환경에서는 heapq가 더 빠르게 동작하므로 heapq를 사용하도록 하자.

파이썬의 힙은 최소 힙으로 구성되어 있으므로 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료된다. 보통 최소 힙 자료구조의 최상단 원소는 항상 가장 작은 원소이기 때문이다.

▶ 최소 힙(Min Heap) - 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속한다.

▶ 최대 힙(Max Heap) - 항상 부모 노드가 자식 노드보다 크기가 큰 자료구조로서 트리 자료구조에 속한다.

[min heap sort.py]

#최소 힙 정렬(오른차순 힙 정렬)

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]

[max heap sort.py]

#최대 힙 정렬

import heapq

def heapsort(iterable):
    r = []
    result = []

    for value in iterable:
        heapq.heappush(r,-value)
    
    for _ in range(len(r)):
        result.append(-heapq.heappop(r))

    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]