[자료구조] Priority Queue

※ 2022년 1월 4일에 작성된 글입니다.

🚦 Priority Queue

우선순위를 가진 항목들을 저장하는 큐

• FIFO가 아니라 우선 순위가 높은 데이터가 먼저 나간다.

Priority Queue의 연산

• insert
  우선순위 큐에 요소를 추가한다.
• delete
  우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다.
• find
  우선순위가 가장 높은 요소를 반환한다.
• isEmpty
  우선순위 큐가 비어있는지 확인한다.

Priority Queue의 구분

• 최소 우선순위 큐
• 최대 우선순위 큐

Priority Queue의 응용 분야

• 시뮬레이션 시스템
• 네트워크 트래픽 제어
• 운영 체제에서의 작업 스케쥴링

Priority Queue의 구현 방법

• 배열(array)
• 연결리스트(linked list)
• 힙(heap)

구현 방법	삽입	삭제
순서 없는 배열	O(1)	O(n)
순서 없는 연결리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결리스트	O(n)	O(1)
힙	O(log n)	O(log n)