자료구조: 우서순위 큐(Priority Queue)와 힙(Heap) 10분 핵심 요약

• 이것이 취업을 위한 코딩테스다 with 파이썬(이코테 2021) 유튜브 영상을 보면서 공부한 자료입니다.
• https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

---

우선순위 큐(Priority Queueu)

• 우선순위 큐는, 우선순위가 가장 높은 데이터를 가장 먼제 삭제하는 자료구조이다.
• 우선순위 큐는 데이터를, 우선순위에 따라 처리하고 싶을 때 사용한다.
  

• 우서순위 큐 라이브러리를 활용한 힙 정렬 구현 예제
• python에서는 heap 라이브러리가 min heap으로 동작하는 것이 default이다.
• heap 라이브러리가 max heap으로 동작하게 하고 싶다면, 데이터를 넣을 때와 꺼낼때 마이너스(-) 부호를 붙여서 코드를 작성하면 된다.

import sys
import heapq
input = sys.stdin.realine

def heapsort(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 = heapsort(arr)

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