우선순위 큐

3. 구현

우선순위 큐는 연관 배열을 사용하여 구현할 수 있다. 가장 간단한 방법은 각 우선순위에 요소 목록을 연결하는 것이다. 연관 리스트나 해시 테이블을 사용하면 요소 추가는 빠르게(O(1)) 할 수 있지만, 요소를 삭제하거나 첫 번째 요소를 참조하려면 모든 키를 탐색해야 해서 느리다(O(''n'')). 균형 이진 탐색 트리를 사용하면 이 세 가지 연산을 모두 O(log ''n'')으로 수행할 수 있어 더 효율적이다.

반 엠데 보아스 트리는 이 세 가지 연산을 O(log log ''n'')으로 더 빠르게 수행할 수 있지만, 큐의 공간 비용이 커지는 단점이 있다.

힙을 사용하면 더 좋은 성능을 낼 수 있다. 이진 힙은 요소 삽입 및 삭제를 O(log ''n'')으로, 첫 번째 요소 참조는 O(1)로 수행한다. 이항 힙은 몇 가지 추가 연산을 제공하지만, 첫 번째 요소 참조에 O(log ''n'')이 걸린다. 피보나치 힙은 삽입, 첫 번째 요소 참조, 우선순위 낮추기 연산을 O(1)의 분할 상환 실행 시간으로, 요소 삭제는 O(log ''n'')으로 수행하여 효율성을 높인다.

3. 1. 단순 구현

4. 우선순위 큐와 정렬 알고리즘의 동등성

우선순위 큐의 의미는 정렬 방법을 자연스럽게 제시한다. 정렬할 모든 요소를 우선순위 큐에 삽입하고 순차적으로 제거하면 정렬된 순서로 나오게 된다. 이것은 실제로 우선순위 큐가 제공하는 추상화 계층을 제거하면 여러 정렬 알고리즘에서 사용되는 절차이다. 이 정렬 방법은 다음과 같은 정렬 알고리즘과 동일하다.

정렬 알고리즘은 우선순위 큐를 구현하는 데에도 사용할 수 있다. 구체적으로, 토럽은 다음과 같이 말한다.^[21]

> 우리는 우선순위 큐를 정렬로 줄이는 일반적인 결정적 선형 공간 감소를 제시하며, 여기서 최대 ''n''개의 키를 키당 ''S''(''n'') 시간에 정렬할 수 있다면, ''delete''와 ''insert''를 ''O''(''S''(''n'')) 시간에 지원하고, ''find-min''을 상수 시간에 지원하는 우선순위 큐가 존재한다.

즉, 키당 ''O''(''S'') 시간에 정렬할 수 있는 정렬 알고리즘이 있다면, 여기서 ''S''는 ''n''과 단어 크기의 함수이며,^[22] 주어진 절차를 사용하여 우선순위가 가장 높은 요소를 꺼내는 데 ''O''(1) 시간이 걸리고, 새 요소를 삽입(및 삭제)하는 데 ''O''(''S'') 시간이 걸리는 우선순위 큐를 만들 수 있다. 예를 들어, ''O''(''n'' log ''n'') 정렬 알고리즘이 있다면, ''O''(1) 꺼내기와 ''O''( log ''n'') 삽입을 가진 우선순위 큐를 만들 수 있다.

5. 라이브러리

우선순위 큐는 여러 프로그래밍 언어에서 표준 라이브러리나 외부 라이브러리를 통해 제공된다.

• C++의 표준 템플릿 라이브러리(STL)는 `std::priority_queue`라는 컨테이너 어댑터 클래스 템플릿을 제공한다. 이는 최대 우선순위 큐를 구현하며, 반복자 접근은 허용하지 않는다. 부스트 라이브러리에도 힙 라이브러리에 구현이 있다. GCC (libstdc++-v3)에서는 이진 힙이 채택되었다.^[30] g++ 확장인 PBDS에는 내부 데이터 구조를 선택할 수 있는 priority_queue가 존재하며, 기본값은 페어링 힙이다.^[31]

• Python의 `heapq` 모듈은 리스트를 기반으로 이진 최소 힙을 구현한다.

• 자바 라이브러리에는 `PriorityQueue` 클래스가 있으며, 이진 힙으로 최소 우선순위 큐를 구현한다. Java 8 현재, 계산량은 다음과 같다.^[32]

• .NET 라이브러리에는 `PriorityQueue` 클래스가 있으며, 배열 기반의 사원 최소 힙을 구현한다.

• 스칼라 라이브러리에는 최대 우선순위 큐를 구현하는 `PriorityQueue` 클래스가 있다.

• Go 라이브러리에는 `container/heap` 모듈이 있으며, 최소 힙을 구현한다.

• 표준 PHP 라이브러리 확장은 `SplPriorityQueue` 클래스를 포함한다.

• 애플(Apple Inc.)의 코어 파운데이션 프레임워크에는 최소 힙을 구현하는 `CFBinaryHeap` 구조체가 있다.

6. 응용

우선순위 큐는 컴퓨터 과학의 여러 분야에서 응용된다.

• 그래프 알고리즘: 다익스트라 알고리즘, 프림 알고리즘 등 최단 경로나 최소 신장 트리를 찾는 알고리즘에 사용된다.
• 데이터 압축: 허프만 부호화와 같이 데이터를 효율적으로 압축하는 데 활용된다.
• 운영 체제: 프로세스 관리, 인터럽트 처리, 부하 분산 등 운영 체제의 핵심 기능에 사용된다.

6. 1. 대역폭 관리

6. 2. 이산 사건 시뮬레이션

6. 3. 그래프 알고리즘

6. 4. 운영 체제

7. 병렬 우선순위 큐

병렬 처리는 우선순위 큐의 속도를 높이는 데 사용될 수 있다. 이를 위해 우선순위 큐 인터페이스에 몇 가지 변경이 필요하다.
동시 병렬 접근 (Concurrent parallel access): 여러 프로세서가 동일한 우선순위 큐에 동시에 접근할 수 있도록 허용한다.

• 문제점:
• 여러 프로세스가 동시에 우선순위 큐에 접근하면, 연산의 의미가 모호해진다. 예를 들어, 두 프로세스가 동시에 가장 높은 우선순위의 요소를 추출하려고 할 때, 같은 요소를 얻어야 하는지, 아니면 다른 요소를 얻어야 하는지 명확하지 않다.
• 여러 프로세스가 동일한 요소에 접근하므로 경합이 발생한다.

• 

• k_extract-min 연산:
• 우선순위 큐에서 k개의 가장 작은 요소를 삭제하고 반환한다.
• 공유 메모리 설정에서 병렬 이진 탐색 트리와 조인 기반 트리 알고리즘을 사용하여 쉽게 구현할 수 있다.
• `k_extract-min`은 O(log n)의 비용이 들고 k개의 가장 작은 요소를 포함하는 트리를 생성하는 이진 탐색 트리에 대한 '분할'에 해당한다.

• k_insert 연산:
• 원래 우선순위 큐와 삽입 배치의 '결합'을 적용하여 적용할 수 있다.
• 배치가 이미 키로 정렬된 경우 `k_insert`는 O(k log (1+n/k)) 비용이 든다.
• 그렇지 않으면 먼저 배치를 정렬해야 하므로 비용은 O(k log n)이 된다.

• 분산 메모리 환경:
• 각 프로세서는 자체 로컬 메모리와 로컬 (순차적) 우선순위 큐를 가진다.
• 전역 (병렬) 우선순위 큐의 요소는 모든 프로세서에 분산된다.
• `k_insert` 연산은 요소를 균일하게 무작위로 프로세서에 할당하여 로컬 큐에 요소를 삽입한다.
• `k_extract-min` 연산은 각 로컬 큐에서 가장 작은 m개의 요소를 제거하여 결과 집합에 수집하고, 병렬 선택을 통해 결과 집합에서 가장 작은 k개의 요소를 결정한다.
• `k_extract-min`의 실행 시간은 O(k/p log(n))로 예상되며, 여기서 k = Ω(p * log(p))이고 n은 우선순위 큐의 크기이다.^[29]

• 

참조

_[1] 서적 Introduction to Algorithms
_[2] 서적 The Algorithm Design Manual Springer Science+Business Media
_[3] 간행물 Preserving order in a forest in less than logarithmic time IEEE Computer Society
_[4] 논문 Surpassing the information theoretic bound with fusion trees
_[5] 서적 Introduction to Algorithms
_[6] 논문 Average Case Analysis of Heap Building by Repeated Insertion http://www.stats.ox.[...] 2016-01-28
_[7] 논문 Self-Adjusting Heaps https://www.cs.cmu.e[...] 1986-02
_[8] 서적 Data Structures and Network Algorithms
_[9] 웹사이트 Binomial Heap {{!}} Brilliant Math & Science Wiki https://brilliant.or[...] 2019-09-30
_[10] 간행물 Optimal purely functional priority queues 1996-11
_[11] 서적 Purely Functional Data Structures
_[12] 간행물 Theory of 2–3 Heaps https://ir.canterbur[...]
_[13] 간행물 Proc. 7th Scandinavian Workshop on Algorithm Theory http://john2.poly.ed[...] Springer-Verlag
_[14] 논문 On the Efficiency of Pairing Heaps and Related Data Structures http://www.uqac.ca/a[...] 1999-07
_[15] 학회 Towards a Final Analysis of Pairing Heaps http://web.eecs.umic[...]
_[16] 논문 Rank-pairing heaps http://sidsen.org/pa[...] 2011-11
_[17] 논문 Fibonacci heaps and their uses in improved network optimization algorithms http://bioinfo.ict.a[...] 1987-07
_[18] 학회 Strict Fibonacci heaps http://www.cs.au.dk/[...]
_[19] 간행물 Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms
_[20] 서적 Data Structures and Algorithms in Java
_[21] 논문 Equivalence between priority queues and sorting
_[22] 웹사이트 Archived copy http://courses.csail[...] 2011-02-10
_[23] 서적 Introduction to Algorithms
_[24] 웹사이트 Prim's Algorithm http://www.geeksforg[...] Geek for Geeks 2012-11-18
_[25] 논문 Fast and lock-free concurrent priority queues for multi-thread systems https://doi.org/10.1[...] 2005
_[26] 간행물 A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention http://www.it.uu.se/[...] 2013
_[27] 간행물 Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016) ACM
_[28] 간행물 Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming ACM
_[29] 서적 Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox Springer International Publishing 2019
_[30] 문서 libstdc++-v3: stl_queue.h https://github.com/g[...]
_[31] 문서 Policy-Based Data Structures: Priority-Queues http://gcc.gnu.org/o[...]
_[32] 문서 PriorityQueue (Java Platform SE 8) http://docs.oracle.c[...]