논문KCI 등재
묵시 다원 AM-힙
Implicit D-Ary AM-Heap
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
주제분류컴퓨터학
초록
본 논문에서는 AM-힙의 다원 버전인 AM(d)-힙이라고 하는 묵시 다원 우선순위 큐를 제안하며, 제안된 AM(d)-힙에서는 삽입에 O(1) 전이시간이 걸리고 삭제 연산에 O(logn) 시간이 걸린다. 실험 결과에 따르면, 전체적으로 d가 4 또는 8일 때 가장 우수한 성능을 나타내었다. 기존의 후위힙과 비교하면 AM(d)-힙이 약 1.5~1.8배 빠른 것으로 나타났다.
Abstract
This paper proposes an implicit d-ary priority queue, called AM(d)-heap that is a generalized version of AM-heap, in which insert operation takes constant amortized time and remove operation takes O(logn) time. According to our experimental results, the best performance was shown when d is 4 or 8. Also, AM(d)-heap is about 1.5～1.8 times faster than the postorder heap.
참고문헌 (12)
- M. Fredman, "Fibonacci heaps and their uses in improved network optimization algorithms", Journal of the ACM, 34(3), pp.596~615 (1987)
- M. Fredman, "The pairing heap : A new form of self-adjusting heap", Algorithmica, 1, pp.111~129 (1986)
- T. J. Stasko, "Pairing heaps : experiments and analysis", Communications of the ACM, 30(3), pp.234~249 (1987)
- S. Bansal, "M-heap : A Modified heap data structure", International Journal of Foundations of Computer Science, 14(3), pp.491~502 (2003)
- J. Williams, "Algorithm 232 Heapsort", Communications of the ACM, 7(1), pp.347~348 (1964)
- E. Horowitz, "Fundamentals of Data Structures in C++" (1995), W. H. Freeman
- S. Carlsson, "An implicit binomial queue with constant insertion time", 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)
- 정해재, "배열 표현을 이용한 M-힙에서 삽입", 삭제 알고리즘, 2006, pp.13(3), 261~266[DOI]
- 정해재, "우선순위 큐 알고리즘 성능 평가", 한국정보기술학회논문지, 8(6), pp.97~103 (2010), 한국정보기술학회
- D. Jones, "An empirical comparison of priority-queue and event-set implementation", Communications of the Association for Computing Machinery, 29(4), pp.300~311 (1986)
관련 논문AI추천
IMI-힙: 상수 삽입 전이 시간 복잡도를 가진 묵시 양단 우선순위 큐정해재한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2019 · 제8권 제2호8 - 힙 ＊ ：빠른 8-원 묵시 우선순위 큐정해재한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2004 · 제11권 제3호배열 표현을 이용한 M-힙에서 삽입/삭제 알고리즘정해재한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2006 · 제13권 제3호상수 삽입 전이 시간을 가지는 양단 우선순위 큐정해재한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2009 · 제16권 제3호4-딥* : 캐쉬를 이용한 빠른 4-원 딥정해재한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2004 · 제11권 제7호우선순위 큐 성능 시험에 관한 연구정해재한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2010 · 제17권 제4호