우선순위 큐 (Priority Queue)

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 우선순위 큐는 인큐할 때는 데이터에 우선순위를 부여하여 추가하고, 디큐할 때 우선순위가 가장 높은 데이터를 꺼낸다.

우선순위 큐는 리스트와 힙을 이용하여 구현할 수 있다.

Python에서 우선순위를 부여하는 큐는 heapq 모듈에서 제공한다. heap에서 data의 인큐는 heapq.heappush(heap, data)로 수행하고, 디큐는 heapq.heappop(heap)으로 수행한다.

힙 (Heap)

힙은 완전 이진 트리 자료구조의 일종이다. 힙에서는 항상 루트 노드를 제거한다. 최소 힙에서는 루트 노드가 가장 작은 값을 가지며, 따라서 값이 가장 작은 데이터를 우선적으로 제거한다. 반면에 최대 힙에서는 루트 노드가 가장 큰 값을 가지며, 값이 가장 큰 데이터를 우선적으로 제거한다.

import sys
import heapq

input = sys.stdin.readline

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

n = int(input())
arr = []

for i in range(n):
    arr.append(int(input()))

res = heap_sort(arr)

for i in range(n):
    print(res[i])

힙은 최대값 또는 최소값을 구하는 문제를 해결하는 데에 사용하기 적합하다.