상수 삽입 전이 시간을 가지는 양단 우선순위 큐
A Double-Ended Priority Queue with O(1) Insertion Amortized Time
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
우선순위 큐는 스케줄링, 정렬, 유전자 검색과 같은 우선순위에 따른 검색, 최단거리 계산과 같은 응용에 사용될 수 있다. 본 논문에서 제안하는 배열을 이용한 양단 우선순위 큐 자료구조는 삽입과 삭제 연산에 각각 O(1) 전이시간과 O(logn) 시간이 걸린다. 본 저자가 알고 있는 한, 지금까지의 배열을 이용한 양단우선순위 큐 알고리즘은 삽입과 삭제에 모두 O(logn) 시간이 걸린다.
Abstract
Priority queues can be used in applications such as scheduling, sorting, retrival based on a priority like gene searching, shortest paths computation. This paper proposes a data structure using array representation for double-ended priority queue in which insertion and deletion takes O(1) amortized time and O(logn) time, respectively. To the author's knowledge, all the published array-based data structures for double ended priority queue support O(logn) time insertion and deletion operations.
참고문헌 (8)
- 정해재, "배열 표현을 이용한 M-힙에서 삽입", 삭제 알고리즘, 2006, pp.13(3), 261~266[DOI]
- D. Mehta, "Handbook of Data Structures and Applications", pp.2005, Chapman & Hall
- S. Bansal, "M-heap: A Modified heap data structures", International Journal of Foundations of Computer Science, 14(3), pp.491~502 (2003)
- S. Carlsson, "An implicit binomial queue with constant insertion time", Proceedings of the 1st Scandinavian Workshop on Algorithm Theory, 통권 : 318, pp.1~13 (1988)
- J. van Leeuwen, "Interval heaps", The Computer Journal, 36(3), pp.209~216 (1993)
- Y. Ding, "On the Complexity of Building an Interval Heap", Information Processing Letters, 50, pp.143~144 (1994)
- H. Jung, "The d-deap*: A fast and simple cache-aligned d-ary deap", Information Processing Letters, 93(2), pp.63~67 (2005)
- E. Horowitz, "Fundamentals of Data Structures in C++" (1995), W. H. Freeman