| 한글제목(Korean Title) |
상수 삽입 전이 시간을 가지는 양단 우선순위 큐 |
| 영문제목(English Title) |
A Double-Ended Priority Queue with O(1) Insertion Amortized Time |
| 저자(Author) |
정해재
Haejae Jung
|
| 원문수록처(Citation) |
VOL 16-A NO. 03 PP. 0217 ~ 0222 (2009. 06) |
한글내용
(Korean Abstract) |
우선순위 큐는 스케줄링, 정렬, 유전자 검색과 같은 우선순위에 따른 검색, 최단거리 계산과 같은 응용에 사용될 수 있다.
본 논문에서 제안하는 배열을 이용한 양단 우선순위 큐 자료구조는 삽입과 삭제 연산에 각각 O(1) 전이시간과 O(logn) 시간이 걸린다. 본 저자가 알고 있는 한, 지금까지의 배열을 이용한 양단우선순위 큐 알고리즘은 삽입과 삭제에 모두 O(logn) 시간이 걸린다. |
영문내용
(English Abstract) |
Priority queues can be used in applications such as scheduling, sorting, retrival based on a priority like gene searching, shortest paths computation. This paper proposes a data structure using array representation for double-ended priority queue in which insertion and deletion takes O(1) amortized time and Ologn) time, respectively. To the author's knowledge, all the published array-based data structures for double ended priority queue support O(logn) time insertion and deletion operations. |
| 키워드(Keyword) |
자료 구조
양단 우선순위 큐
힙
전이 시간 복잡도
Data Structure
Double-Ended Priority Queue
Heap
Amortized Time Complexity
|
| 파일첨부 |
PDF 다운로드
|
