배열 표현을 이용한 M-힙에서 삽입/삭제 알고리즘
Insertion/Deletion algorithms on M-heap with an array representation
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
스케줄링, 정렬, 및 최단 거리 계산 네트워크 문제 등과 같은 응용에 이용될 수 있는 우선 순위 큐 중, 피보나치 힙, 페어링 힙, 및 M-힙은 포인터를 이용하는 자료 구조이다. 본 논문에서는 [1]에서 문제점으로 남겨두었던 M-힙을 배열을 이용하여 표현한 MA-힙(M-heap with an array representation)를 제안한다. MA-힙은 M-힙과 동일한 시간 복잡도인 O(1) 삽입 전이 시간과 O(logn) 삭제 시간 복잡도를 가지며, 단순한 전통적인 힙에 근거하고 있기 때문에 [5]에서 제안된 힙보다 구현이 매우 용이하다.
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.
참고문헌 (9)
- "M-heap:A Modified heap data structures", 14(3), pp.491~502 (2003)
- M. Fredman, "Fibonacci heaps and their uses in improved network optimization algorithms", 34(3), pp.596~615 (1987)
- M. Fredman, "The pairing heap:A new form of self-adjusting heap", 1, pp.111~129
- T.J. Stasko, "Pairing heaps:experiments and analysis", 30(3), pp.234~249 (1987)
- S. Carlsson, "An implicit binomial queue with constant insertion time", 318, pp.1~13
- E. Horowitz, "Fundamentals of Data Structures in C++" (1995)
- D. Mehta, "Handbook of Data Structures and Applications" (2005), Chapman & Hall[DOI]
- A. LaMarca, "The Influence of Caches on the Performance of Heaps", 1(4), pp.1~32 (1996)
- H. Jung, "The d-deap*:A fast and simple cache-aligned d-ary deap", 93(2), pp.63~67 (2005)