배열 표현을 이용한 M-힙에서 삽입/삭제 알고리즘 = Insertion/Deletion algorithms on M-heap with an array representation

국문 초록 (Abstract)

스케줄링, 정렬, 및 최단 거리 계산 네트워크 문제 등과 같은 응용에 이용될 수 있는 우선 순위 큐 중, 피보나치 힙, 페어링 힙, 및 M-힙은 포인터를 이용하는 자료 구조이다. 본 논문에서는 [1]에서 문제점으로 남겨두었던 M-힙을 배열을 이용하여 표현한 MA-힙(M-heap with an array representation)를 제안한다. MA-힙은 M-힙과 동일한 시간 복잡도인 O(1) 삽입 전이 시간과 O(logn) 삭제 시간 복잡도를 가지며, 단순한 전통적인 힙에 근거하고 있기 때문에 [5]에서 제안된 힙보다 구현이 매우 용이하다.

다국어 초록 (Multilingual Abstract)

Priority queues can be used in applications such as scheduling, sorting, and shortest path network problem. Fibonacci heap, pairing heap, and M-heap are priority queues based on pointers. This paper proposes a modified M-heap with an array representation, called MA-heap, that resolves the problem mentioned in [1]. The MA-heap takes O(1) amortized time and O(logn) time to insert an element and delete the max/min element, respectively. These time complexities are the same as those of the M-heap. In addition, it is much easier to implement an MA-heap than a heap proposed in [5] since it is based on the simple traditional heap.

참고문헌 (Reference)

1 M. Fredman, "The pairing heap:A new form of self-adjusting heap" 1 : 111-129, Mar.1986.

2 H. Jung, "The d-deap*:A fast and simple cache-aligned d-ary deap" 93 (93): 63-67, 2005.Jan.

3 A. LaMarca, "The Influence of Caches on the Performance of Heaps" 1 (1): 1-32, 1996

4 T.J. Stasko, "Pairing heaps:experiments and analysis" 30 (30): 234-249, 1987.

5 "M-heap:A Modified heap data structures" 14 (14): 491-502, 2003

6 D. Mehta, "Handbook of Data Structures and Applications" Chapman & Hall/CRC, New York 2005

7 E. Horowitz, "Fundamentals of Data Structures in C++" 1995.

8 M. Fredman, "Fibonacci heaps and their uses in improved network optimization algorithms" 34 (34): 596-615, 1987.

9 S. Carlsson, "An implicit binomial queue with constant insertion time" 318 : 1-13, July.1988.