모노톤 우선 순위 대기열

컴퓨터 과학에서 단조로운 우선순위 큐는 단조로운 시퀀스를 형성하기 위해 추출된 항목의 우선순위가 필요한 우선순위 큐 추상적인 데이터 유형의 변형이다.즉, 연속적으로 추출한 각 항목이 최소 우선순위(최소 히프)인 우선순위 큐의 경우, 최소 우선순위는 단조롭게 증가해야 한다.반대로 최대 heap의 경우 최대 우선순위는 단조롭게 감소해야 한다.단조로움 가정은 자연스럽게 우선순위 대기열의 몇 가지 적용에서 발생하며, 특정 유형의 우선순위 대기열을 가속화하기 위한 단순화 가정으로 사용될 수 있다.^[1]^{: 128}

단조로운 우선 순위 대기열에서 필요하고도 충분한 조건은 가장 최근에 추출한 우선 순위보다 낮은 우선 순위를 가진 요소를 추가하려고 시도하지 않는 것이다.

적용들

네트워크 시간 초과 또는 이산 이벤트 시뮬레이션과 같이 시간순으로 이벤트를 정렬할 때 모노톤 우선 순위 대기열이 자연스럽게 발생한다.이벤트는 미래의 어느 시점에 어떤 행동을 스케줄링하게 할 수 있지만, (실제 또는 시뮬레이션) 인과관계는 과거의 행동을 스케줄링하려는 시도를 무의미하게 만든다.

최단 경로 문제에 대한 Dijkstra 알고리즘에서, 주어진 가중 그래프의 정점을 시작 정점으로부터의 거리에 의해 증가된 순서로 추출하고, 우선 순위 대기열을 사용하여 시작 정점에 가장 가까운 나머지 정점을 결정한다.따라서 이 애플리케이션에서 우선 순위 대기열 작업은 단조롭다.

마찬가지로 계산 기하학에서 스위프 라인 알고리즘에서는 스위프 라인이 관심 지점을 통과하는 이벤트는 교차 지점의 좌표에 의해 우선순위가 정해지며, 이러한 이벤트는 단조로운 순서로 추출된다.단조 추출 순서는 또한 분기와 바운드의 베스트 첫 번째 버전에서도 발생한다.^[1]^{: 128}

데이터 구조

비모노톤 추출 작업을 처리할 수 있는 우선순위 대기열도 모노톤 추출 작업을 처리할 수 있지만, 일부 우선순위 대기열은 모노톤 추출에만 작동하거나 모노톤일 때 더 잘 작동하도록 특수화된다.예를 들어 버킷 대기열은 우선 순위에 따라 인덱싱된 배열로 구성된 단순 우선 순위 대기열 데이터 구조로, 각 어레이 셀에는 해당 우선 순위가 있는 항목의 버킷이 포함되어 있다.추출-민 작업은 비어 있지 않은 첫 번째 버킷에 대해 순차적인 검색을 수행하고 해당 버킷에서 임의 항목을 선택하십시오.비모노톤 추출의 경우, 각 추출물 최소 작동은 배열 길이(별도의 우선 순위 수)에 비례하는 시간(최악의 경우)이 소요된다.그러나 단조로운 우선 순위 대기열로 사용할 경우 다음 비어 있지 않은 버킷에 대한 검색은 어레이의 시작보다는 가장 최근의 이전 추출-min 작업의 우선 순위에서 시작할 수 있다.이 최적화는 일련의 연산 순서에 대한 총 시간을 (비단조적 사례에서와 같이) 이 두 수량의 곱이 아니라 연산 수와 배열 길이의 합계에 비례하게 한다.^[2]

Cherkassky, Goldberg & Silverstein(1999)은 기존의 힙 우선 순위 대기열과 함께 다단계 버킷을 기반으로 정수 우선 순위가 있는 모노톤 우선 순위 대기열을 위한 힙-온-탑(HOT) 대기열이라고 불리는 더 복잡한 체계를 설명한다.그들은 이 방법을 사용하여 정수 우선순위를 가진 항목을 $0$ 부터 파라미터 $C$ 까지의 범위에서 유지할 수 있는 구조를 얻는다.핫 대기열은 삽입 또는 감소 우선순위 작업당 일정한 시간을 사용하고 상각된 $O((\log C)^{1/3}(\log \log C)^{1/2})$ O $O((\log C)^{1/3}(\log \log C)^{1/2})$ ( $O((\log C)^{1/3}(\log \log C)^{1/2})$ $O((\log C)^{1/3}(\log \log C)^{1/2})$ $O((\log C)^{1/3}(\log \log C)^{1/2})$ ) $O((\log C)^{1/3}(\log \log C)^{1/2})$ / 3 $O((\log C)^{1/3}(\log \log C)^{1/2})$ ( $O((\log C)^{1/3}(\log \log C)^{1/2})$ $O((\log C)^{1/3}(\log \log C)^{1/2})$ $O((\log C)^{1/3}(\log \log C)^{1/2})$ C ) $O((\log C)^{1/3}(\log \log C)^{1/2})$ / $O((\log C)^{1/3}(\log \log C)^{1/2})$ ) ${\displaystyle$ O $(\log C)^{1/3}(\log \log C)^{1/2}$ 을 추출분 작업당 사용한다 $O((\log C)^{1/3}(\log \log C)^{1/2})$ .^[3]Raman(1996)의 또 다른 관련 구조는 우선순위가 기계 정수가 될 수 있도록 하며, 상각된 $O({\sqrt {\log n\log \log n}})$ O $O({\sqrt {\log n\log \log n}})$ $O({\sqrt {\log n\log \log n}})$ $O({\sqrt {\log n\log \log n}})$ $O({\sqrt {\log n\log \log n}})$ $O({\sqrt {\log n\log \log n}})$ $O({\sqrt {\log n\log \log n}})$ $){\sqrt{\log$ n $\log \log$ n $}}$ 을(를) 갖는 n $항목$ 의 우선 순위 대기열에서 추출-min 연산을 통해 다시 일정한 시간 삽입 및 감소 우선 순위 연산을 허용한다 $O({\sqrt {\log n\log \log n}})$ ^[4]이러한 결과는 정수 에지 가중치가 있는 그래프에 대한 Dijkstra 알고리즘의 해당 속도 상승을 이끈다.

참조

^ ^a ^b Mehlhorn, Kurt; Sanders, Peter (2008). "Priority queues" (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer.
^ Skiena, Steven S. (1998), The Algorithm Design Manual, Springer, p. 181, ISBN 978-0-387-94860-7.
^ Cherkassky, Boris V.; Goldberg, Andrew V.; Silverstein, Craig (August 1999), "Buckets, heaps, lists, and monotone priority queues", SIAM Journal on Computing, 28 (4): 1326–1346 (electronic), CiteSeerX 10.1.1.49.8244, doi:10.1137/S0097539796313490, MR 1681014.
^ Raman, Rajeev (1996), "Priority queues: small, monotone and trans-dichotomous" (PDF), Algorithms—ESA '96 (Barcelona), Lecture Notes in Computer Science, vol. 1136, Berlin: Springer, pp. 121–137, doi:10.1007/3-540-61680-2_51, MR 1469229.

[mehlhorn-1] Mehlhorn, Kurt; Sanders, Peter (2008). "Priority queues" (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer.

[2] Skiena, Steven S. (1998), The Algorithm Design Manual, Springer, p. 181, ISBN 978-0-387-94860-7.

[3] Cherkassky, Boris V.; Goldberg, Andrew V.; Silverstein, Craig (August 1999), "Buckets, heaps, lists, and monotone priority queues", SIAM Journal on Computing, 28 (4): 1326–1346 (electronic), CiteSeerX 10.1.1.49.8244, doi:10.1137/S0097539796313490, MR 1681014.

[4] Raman, Rajeev (1996), "Priority queues: small, monotone and trans-dichotomous" (PDF), Algorithms—ESA '96 (Barcelona), Lecture Notes in Computer Science, vol. 1136, Berlin: Springer, pp. 121–137, doi:10.1007/3-540-61680-2_51, MR 1469229.

[1]

[2]

[3]

[4]

Search

모노톤 우선 순위 대기열

네임스페이스

더

적용들

데이터 구조

참조