IMI-Heap: An Implicit Double-Ended Priority Queue with Constant Insertion Amortized Time Complexity


KIPS Transactions on Computer and Communication Systems, Vol. 8, No. 2, pp. 29-34, Feb. 2019
https://doi.org/10.3745/KTCCS.2019.8.2.29,   PDF Download:
Keywords: Double-Ended Priority Queue, Implicit Heap, Amortized Time Complexity, Data Structures
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.


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. Jung, "IMI-Heap: An Implicit Double-Ended Priority Queue with Constant Insertion Amortized Time Complexity," KIPS Transactions on Computer and Communication Systems, vol. 8, no. 2, pp. 29-34, 2019. DOI: https://doi.org/10.3745/KTCCS.2019.8.2.29.

[ACM Style]
Haejae Jung. 2019. IMI-Heap: An Implicit Double-Ended Priority Queue with Constant Insertion Amortized Time Complexity. KIPS Transactions on Computer and Communication Systems, 8, 2, (2019), 29-34. DOI: https://doi.org/10.3745/KTCCS.2019.8.2.29.