[코테] 우선순위 큐 (Priority Queue)

우선순위 큐란?

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조, 데이터를 우선순위에 따라 처리하고 싶을 때 사용합니다.
예시 ) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우

• 자료구조 종류와 추출되는 데이터

1. 스택 (Stack) : 가장 나중에 삽입된 데이터(LILO)
2. 큐 (Queue) : 가장 먼저 삽입된 데이터 (FIFO)
3. 우선순위 큐 (Priority Queue) : 가장 우선순위가 높은 데이터

• 우선순위 큐의 구현 방법 2가지

1. 단순한 리스트 이용
2. 힙(heap) 이용

• 데이터의 개수가 N개일 때, 구현 방식에 따른 시간 복잡도
  

• 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일합니다. (힙 정렬)
  -> 이 경우의 시간 복잡도는 O(NlogN)

  Heap 의 특징

• 힙은 완전 이진 트리 자료구조의 일종
  - 완전 이진트리란?
  루트 노트부터 시작해서 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리

• 힙에서는 항상 루트 노드를 제거

• 최소 힙 (min heap)
  - 루트 노드가 가장 작은 값

  • 값이 작은 데이터가 가장 먼저 제거

• 최대 힙 (max heap)
  - 루트 노드가 가장 큰 값

  • 값이 가장 큰 데이터가 우선적으로 제거
    

우선순위 큐 라이브러리 이용한 heap sort

# -*- coding: utf-8 -*-
import sys
import heapq
input = sys.stdin.readline

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])

참고 : https://www.youtube.com/watch?v=AjFlp951nz0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=11