PYTHON에서는 Priority Queue를 다루기 위해 2개의 lib 존재
1. Priority Queue
2. heapq

Priority Queue(우선순위 큐)

• Priority Queue는 우선순위가 가장 높은 데이터를 가장 먼저 삭제
• 특정 조건을 기반으로 데이터 출력시킬 때 효과적
  • ex) 가치가 제일 높은, 거리가 제일 짧은 등
    
    
• python lib
  • 기본 list와는 별개의 자료구조
  • 종류
    • PriorityQueue
    • heapq
  • heapq가 더 빠르게 동작하기 때문에 권장
  • 사용한 경우 최대 간선의 개수(E)만큼 연산이 수행
    - 빅오 표기법 : O(ElogV)
    - 모든 노드가 연결이 되어있다고 해도 중복 간선을 제거한다면 E는 항상 V2보다 작다
    
    
• 데이터 묶음으로 우선순위 큐에 넣을 경우 앞에 데이터가 우선 가치 순위
  • EX) (A,B)의 경우 A 가치를 우선적으로 기준으로 삼는다
    
    
• 참고
  • stack : 선입 후출
  • queue : 선입 선출
  • Priority Queue : 가장 우선순위가 높은 데이터 출력

Heap

• Priority Queue를 구현하기 위하여 사용하는 자료구조 중에 하나
  • 자료구조 중에 하나라지만 python의 경우 개별적으로 존재하는 자료구조가 아닌 list에 함수를 이용해 heap처럼 다루게 도와주는 것
  • 노드 수가 많아질수록 list 사용하는 경우보다 훨씬 유리한 모습 보임
    
    
• Max Heap(최대 힙), Min Heap(최소 힙) 사용
  • Max Heap : 값이 큰 데이터가 먼저 삭제
  • Min Heap : 값이 작은 데이터가 먼저 삭제
    - python lib의 경우 최소 힙 기반으로 lib 구성
    - 최대 힙으로 사용 목적으로 값의 (-)붙여 작업하고 이 후에 다시 (-)붙여주는 방식도 존재
    
    
• list보다 효율적으로 삽입 삭제 가능
  • 빅오 표기법으로 list의 시간복잡도의 경우 O(N2), Heap의 경우 O(NlogN)