우선순위 큐

우선순위 큐는 평범한 큐나 스택과 비슷한 축약 자료형이다. 그러나 각 원소들은 우선순위를 갖고 있다. 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다

 

우선순위 큐가 힙이라는 것은 널리 알려진 오류이다. 우선순위 큐는 "리스트"나 "맵"과 같이 추상적인 개념이다; 마치 리스트는 연결 리스트나 배열로 구현될 수 있는 것과 같이, 우선순위 큐는 힙이나 다양한 다른 방법을 이용해 구현될 수 있다.

우선순위 큐는 최소한 다음의 연산이 지원 되어야 한다:

• insert_with_priority: 하나의 원소를 우선순위를 지정하여 큐에 추가한다.
• pull_highest_priority_element: 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 이를 반환한다.이것은 "pop_element(Off)", "get_maximum_element", 또는 "get_front(most)_element"라고 알려져 있기도 하다.우선순위의 순서를 뒤집어 낮은 값의 것을 높은 우선도로 생각하는 경우도 있는데, 이것은 "get_minimum_element"라고 알려져 있고, "get-min"이라고 쓰기도 한다.pull_highest_priority_element는 "peek_at_highest_priority_element"와 "delete_element" 함수로 나뉘어 정의될 수 있다.

이들 연산 이외에도 더 복잡한 연산을 지원하는 고급 기능들을 구현할 수도 있다. 예로 pull_lowest_priority_element라는 연산을 정의해 처음 높은 우선순위나 낮은 우선순위의 원소들을 살펴보는 기능을 만들 수도 있고, 큐를 모두 비우거나, 큐의 부분집합을 비우거나, 여러 원소들을 한번에 삽입하거나, 둘 이상의 큐를 하나로 병합하거나, 임의의 원소의 우선순위를 증가시키는 등의 연산을 정의할 수도 있다.