IMI-힙: 상수 삽입 전이 시간 복잡도를 가진 묵시 양단 우선순위 큐
IMI-Heap: An Implicit Double-Ended Priority Queue with Constant Insertion Amortized Time Complexity
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
우선순위 큐은 근본적인 자료 구조 중의 하나이며 오랫동안 많은 연구가 이루어여 왔다. 본 논문에서는 IMI-힙이라고 하는 묵시 양단 우선순위 큐를 제안한다. 제안된 IMI-힙에서는 삽입에 O(1) 전이시간이 걸리고 최소값과 최대값 삭제 연산에 각각 O(logn) 시간이 걸린다. 기존에 발표된 묵시 양단 우선순위 큐는 삽입과 최소/최대값 삭제에 모두 O(logn) 시간이 걸리는 것으로 본 저자는 알고 있다. 따라서 제안된 IMI-힙은 삽입 시간 복잡도에 있어서 기존의 힙보다 우수하다.
Abstract
Priority queues, one of the fundamental data structures, have been studied for a long time by computer scientists. This paper proposes an implicit double-ended priority queue, called IMI-heap, in which insert operation takes constant amortized time and each of removal operation of the minimum key or the maximum key takes O(logn) time. To the author’s knowledge, all implicit double-ended priority queues that have been published, perform insert, removeMin and removeMax operations in O(logn) time each. So, the proposed IMI-heap is superior than the published heaps in terms of insertion time complexity.The abstract should concisely state what was done, how it was done, principal results, and their significance.
참고문헌 (10)
- E. Horowitz, "Fundamentals of Data Structures in C++" (1995), W. H. Freeman
- S. Carlsson, "An implicit binomial queue with constant insertion time, in Proceedings of the 1st Scandinavian Workshop on Algorithm Theory", Lecture Notes in Computer Science, 318, pp.1~13 (1988)
- N. Harvey, "The Post-order heap", Proceedings of the Third International Conference on Fun with Algorithms(FUN) (2004)
- H. Jung, "A Simple Array Version of M-heap", International Journal of Foundations of Computer Science, 25(1), pp.67~88 (2014)
- H. Jung, "The d-deap : A fast and simple cache-aligned d-ary deap", Information Processing Letters, 93(2), pp.63~67 (2005)
- 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)
- "Data Structures, Algorithms, & Applications in Java: Double-Ended Priority Queues"[URL]
- S. Bansal, "M-heap : A Modified heap data structures", International Journal of Foundations of Computer Science, 14(3), pp.491~502 (2003)
- 정해재, "상수 삽입 전이 시간을 가지는 양단 우선순위 큐", 정보처리학회논문지. 컴퓨터 및 통신시스템, 16(3), pp.217~222 (2009), 한국정보처리학회