우선순위 큐 : heapq

골드5 강의실 배정 문제를 풀다 로직은 맞는데
시간초과가 계속 떠서 문제의 카테고리를 보니
우선순위 큐가 있었음.
큐는 아는데 우선순위 큐는 뭐지;; 그래서 정리해봄.

우선순위 큐 ?

그냥 큐는 FIFO (First In First Out) 선입선출 구조인데,
우선순위 큐는 우선순위가 높은 값이 먼저 나가는 구조임.

우선순위 큐는 보통 Heap으로 구현하는데 
Heap은 완전 이진 트리 구조로 우선순위가 높은 값이 루트이고,
그 다음 우선순위 값들이 오른쪽 왼쪽 자식으로 뻗어나가는 구조임.

push와 pop으로 값을 넣고, 루트 값을 뽑을 수 있으며,
heap은 넣고, 뽑을 때 모듈에서 자동으로 우선순위를 정렬 해줌.

So, 왜 씀?

완전 이진 트리 구조이기 때문에 값을 추가, 삭제할 때 
각각 항상 O(logN)의 시간 복잡도를 가진다. 

결론 : 굉장히 빠르기 때문

ㅇㅇ 근데, 어캐 씀?

Python에서 사용하는 방법은 

import heapq 로 힙 모듈을 임포트 해주고, 

값 추가 : heapq.heappush(리스트, 값)
루트 추출 : heapq.heappop(리스트)

• 추가로 파이썬의 heapq는 기본적으로 min heap 구조
  min heap == 가장 작은 값이 루트

결론 : heap 모듈 쓰자 ㅈㄴ 빠르다.