ps:monotonic_priority_queue
Monotonic Priority Queue
- 우선순위큐에서, extract-min 연산으로 추출되는 값이 항상 모노토닉할 때 사용할 수 있는 구조. 일반적인 우선순위큐보다 쓰는 데에 제약이 걸린 대신에 좀더 빠르게 동작하도록 구현할 수 있다.
- extract-min 연산으로 추출되는 값이 항상 모노토닉하다는 조건이 성립하는 대표적인 활용 예제는 다익스트라 알고리즘이다.
- Monotonic Priority Queue에 해당되는 데이터구조로는 Radix Heap 이 있다.
Radix Heap
- Radix heap 를 참고
- 모든 키가 정수여야 한다는 조건이 필요하다
- 시간 복잡도는 버켓의 갯수 B에 영향을 받는다. B는 O(logC) 이고, C는 키의 최댓값과 최솟값의 차이이다. 32bit 정수를 대상으로 동작한다면 최대 32라고 봐도 된다.
- 위키피디아에 의하면 insert는 O(B), extract-min은 amortized O(1), decrease-key도 amortized O(1)이라고 한다. 이대로 다익스트라 알고리즘에 적용한다면 시간복잡도가 O(|V|+|E|)가 될 것이다.
- 하지만 보통 decrease-key 를 구현하지 않는 것 같다 (참고 구현체: https://github.com/iwiwi/radix-heap). 그렇게 insert와 extract_min으로만 다익스트라 알고리즘을 구현한다면 O(|E|*B)가 될텐데, 이것은 그냥 바이너리 힙을 썼을때의 O(|E|log|V|)보다 빠르기 힘들다.
- 그럼에도 불구하고, https://github.com/iwiwi/radix-heap 에서는 실용적인 문제들에 대해서 std::priority_queue 보다 약 2배 빨랐다고 한다
- https://blog.naver.com/jinhan814/222507238041 에서는 BOJ 문제에 제출했을때 시간 차이가 거의 없었다고 한다.
- 여기서 유추할때, 파이썬에서 이걸 구현해봤자 PS용도에서 heapq보다 빨라질 가능성은 거의 없다고 생각된다. 구현도 안해보기로 했다.
ps/monotonic_priority_queue.txt · 마지막으로 수정됨: 2022/04/03 13:13 저자 teferi
토론