우선순위(priority) 큐는 주어진 점수에 따라 항목을 정렬해 탐색하는 자료구조.

• 스택과 큐는 데이터가 삽입된 순서만 고려했지만, 우선순위 큐는 추가 정보, 즉 우선순위를 사용해 탐색 순서를 결정
  • 긴급한 요청을 먼저 처리할 수 있다.
• 힙은 우선순위 큐의 핵심 연산을 극도로 효율적으로 만든다.

1. 우선순위 큐

우선순위 큐는 항목 집합을 저장하고, 가장 높은 우선순위를 가진 항목을 쉽게 탐색하게 해준다.

• 우선순위 큐는 동적이며, 삽입과 탐색을 혼용해도 잘 작동한다.
• 우선순위가 지정된 작업 목록에서 항목을 추가하거나 제거할 수 있어야 한다.

가장 기본적인 형태에서 우선순위 큐는 몇 가지 주요 연산을 지원한다.

• 항목과 그 항목에 대한 우선순위 점수를 추가한다.
• 가장 높은 우선순위를 가진 항목을 찾는다(큐가 비어 있으면 null을 반환한다).
• 가장 높은 우선순위를 가진 항목을 제거한다(큐가 비어 있으면 null을 반환한다).

또 우선순위 큐가 비어 있는지를 확인하거나 현재 저장된 항목 수를 반환하는 기능을 추가할 수도 있다.

원시 자료 구조인 정렬된 연결 리스트나 정렬된 배열 같은 구조를 사용해 우선순위 큐를 구현할 수도 있지만, 이상적인 방법은 아니다. 원시 자료 구조를 사용할 때도 우선순위에 따라 새 항목을 목록에 추가한다.

정렬된 연결 리스트는 우선순위가 가장 높은 항목을 리스트의 맨 앞에 두기 때문에 탐색이 아주 쉽다.

• 첫 번째 원소를 확인하기만 하면 우선순위 큐의 길이에 관계없이 상수 시간에 최우선 항목을 탐색할 수 있다.