목차

1. 우선순위 큐 ADT

(1) 소개

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료 구조이다.

우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저 나가는 형태의 자료 구조이다.

(2) 우선순위 큐의 연산

<aside> 💡 주요 연산

• Insert(key, data)
  • key에 따른 데이터를 우선순위 큐에 삽입한다.
  • 항목들은 key에 따라 정렬된다.
• DeleteMin / DeleteMax
  • DeleteMin: 가장 작은 key를 가진 항목을 삭제하고 리턴한다.
  • DeleteMax: 가장 큰 key를 가진 항목을 삭제하고 리턴한다.
• GetMininum / GetMaximum
  • 가장 작은/큰 키를 가진 항목을 삭제하지 않고 리턴한다. </aside>

<aside> 💡 보조 연산

• kth-Smallest/kth-Largest
  • 우선순위 큐에서 k번째로 작거나/큰 키를 리턴한다.
• size
  • 우선순위 큐 안의 항목의 개수를 리턴한다.
• Heap Sort
  • 우선순위 큐의 항목을 우선순위(키)에 따라 정렬한다. </aside>

(3) 적용 사례

• 데이터 압축: 허프만(Huffman) 코딩 알고리즘
• 최단 거리 알고리즘: 다익스트라(Dijkstra)의 알고리즘
• 최소 신장 트리 알고리즘: 프림(Prim)의 알고리즘
• 이벤트 지향 시뮬레이션: 줄 서 있는 고객들
• 선택 문제: k번째 작은 항목 찾기
• 운영체제에서의 작업 스케줄링