Insertion/Deletion algorithms on M-heap with an array representation


The KIPS Transactions:PartA, Vol. 13, No. 3, pp. 261-266, Jun. 2006
10.3745/KIPSTA.2006.13.3.261,   PDF Download:

Abstract

Priority queues can be used in applications such as scheduling, sorting, and shortest path network problem. Fibonacci heap, pairing heap, and M-heap are priority queues based on pointers. This paper proposes a modified M-heap with an array representation, called MA-heap, that resolves the problem mentioned in [1]. The MA-heap takes O(1) amortized time and O(logn) time to insert an element and delete the max/min element, respectively. These time complexities are the same as those of the M-heap. In addition, it is much easier to implement an MA-heap than a heap proposed in [5] since it is based on the simple traditional 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. J. Jung, "Insertion/Deletion algorithms on M-heap with an array representation," The KIPS Transactions:PartA, vol. 13, no. 3, pp. 261-266, 2006. DOI: 10.3745/KIPSTA.2006.13.3.261.

[ACM Style]
Hae Jae Jung. 2006. Insertion/Deletion algorithms on M-heap with an array representation. The KIPS Transactions:PartA, 13, 3, (2006), 261-266. DOI: 10.3745/KIPSTA.2006.13.3.261.