우선순위 큐 Priority Queue (미완)

우선순위큐

• 사용목적 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제
• 상태 : 우선순위에 따라 정렬되어있음
• 시간복잡도 (heap사용시)
  • 삭제 : $O(log_2n)$
  • 삽입 : $O(log_2n)$

• 다른 자료구조와 삭제기준 비교

  자료구조	추출되는 데이터
  stack	가장 나중에 삽입된 데이터
  queue	가장 먼저 삽입된 데이터
  priority queue	가장 우선순위가 높은 데이터

• 일반적으로 최소힙(Min Heap) 혹은 최대 힙(Max Heap)을 사용하여 구현

  • 최소힙 : 값이 낮은 데이터 먼저 삭제
  • 최대힙 : 값이 큰 데이터 먼저 삭제

• python에선 PriorityQueue / heapq로 가능하지만 일반적으로 heapq가 빠름

레퍼런스

chanhuiseok님의 깃헙블로그 : 자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)