우선순위 큐

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

우선순위 큐가 이라는 것은 널리 알려진 오류이다. 우선순위 큐는 "리스트"나 "맵"과 같이 축약된 개념이다; 마치 리스트연결 리스트행렬로 구성될 수 있는 것과 같이, 우선순위 큐는 힙이나 다양한 다른 방법을 이용해 구성될 수 있다.

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

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

더 고급의 기능에서는 더 복잡한 연산을 지원할 수 있다. 예로 pull_lowest_priority_element라는 연산은 처음 몇몇의 높은 우선순위나 낮은 우선순위의 원소들을 검사하고, 큐를 비우고, 큐의 부분집합을 비우고, 배치 삽입을 수행하고, 둘 이상의 큐를 하나로 병합하고, 임의의 원소의 우선순위를 증가시키는 등의 연산을 할 수 있다.