정보처리학회 논문지 컴퓨터 및 통신시스템
Current Result Document :
| 한글제목(Korean Title) |
IMI-힙: 상수 삽입 전이 시간 복잡도를 가진 묵시 양단 우선순위 큐 |
| 영문제목(English Title) |
IMI-Heap: An Implicit Double-Ended Priority Queue with Constant Insertion Amortized Time Complexity |
| 저자(Author) |
정해재
Haejae Jung
|
| 원문수록처(Citation) |
VOL 08 NO. 02 PP. 0029 ~ 0034 (2019. 02) |
한글내용
(Korean Abstract) |
우선순위 큐은 근본적인 자료 구조 중의 하나이며 오랫동안 많은 연구가 이루어여 왔다. 본 논문에서는 IMI-힙이라고 하는 묵시 양단 우선순위 큐를 제안한다. 제안된 IMI-힙에서는 삽입에 O(1) 전이시간이 걸리고 최소값과 최대값 삭제 연산에 각각 O(logn) 시간이 걸린다. 기존에 발표된 묵시 양단 우선순위 큐는 삽입과 최소/최대값 삭제에 모두 O(logn) 시간이 걸리는 것으로 본 저자는 알고 있다. 따라서 제안된 IMI-힙은 삽입 시간 복잡도에 있어서 기존의 힙보다 우수하다.
|
영문내용
(English 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.
|
| 키워드(Keyword) |
양단 우선순위 큐
묵시 힙
전이 시간 복잡도
자료 구조
Double-Ended Priority Queue
Implicit Heap
Amortized Time Complexity
Data Structures
|
| 파일첨부 |
PDF 다운로드
|
