Implicit D-Ary AM-Heap


KIPS Transactions on Computer and Communication Systems, Vol. 7, No. 12, pp. 289-294, Dec. 2018
https://doi.org/10.3745/KTCCS.2018.7.12.289,   PDF Download:
Keywords: Priority Queue, Implicit Heap, Amortized Time Complexity, Data Structures
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.


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, "Implicit D-Ary AM-Heap," KIPS Transactions on Computer and Communication Systems, vol. 7, no. 12, pp. 289-294, 2018. DOI: https://doi.org/10.3745/KTCCS.2018.7.12.289.

[ACM Style]
Haejae Jung. 2018. Implicit D-Ary AM-Heap. KIPS Transactions on Computer and Communication Systems, 7, 12, (2018), 289-294. DOI: https://doi.org/10.3745/KTCCS.2018.7.12.289.