A Double-Ended Priority Queue with O(1) Insertion Amortized Time


The KIPS Transactions:PartA, Vol. 16, No. 3, pp. 217-222, Jun. 2009
10.3745/KIPSTA.2009.16.3.217,   PDF Download:

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.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
H. J. Jung, "A Double-Ended Priority Queue with O(1) Insertion Amortized Time," The KIPS Transactions:PartA, vol. 16, no. 3, pp. 217-222, 2009. DOI: 10.3745/KIPSTA.2009.16.3.217.

[ACM Style]
Hae Jae Jung. 2009. A Double-Ended Priority Queue with O(1) Insertion Amortized Time. The KIPS Transactions:PartA, 16, 3, (2009), 217-222. DOI: 10.3745/KIPSTA.2009.16.3.217.