정보처리학회 논문지 컴퓨터 및 통신시스템
Current Result Document :
| 한글제목(Korean Title) |
묵시 다원 AM-힙 |
| 영문제목(English Title) |
Implicit D-Ary AM-Heap |
| 저자(Author) |
정해재
Haejae Jung
|
| 원문수록처(Citation) |
VOL 07 NO. 12 PP. 0289 ~ 0294 (2018. 12) |
한글내용
(Korean Abstract) |
본 논문에서는 AM-힙의 다원 버전인 AM(d)-힙이라고 하는 묵시 다원 우선순위 큐를 제안하며, 제안된 AM(d)-힙에서는 삽입에 O(1)전이시간이 걸리고 삭제 연산에 O(logn) 시간이 걸린다. 실험 결과에 따르면, 전체적으로 d가 4 또는 8일 때 가장 우수한 성능을 나타내었다. 기존의 후위힙과 비교하면 AM(d)-힙이 약 1.5~1.8배 빠른 것으로 나타났다.
|
영문내용
(English 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.
|
| 키워드(Keyword) |
우선순위 큐
묵시 힙
전이 시간 복잡도
자료 구조
Priority Queue
Implicit Heap
Amortized Time Complexity
Data Structures
|
| 파일첨부 |
PDF 다운로드
|
