A SIMPLE ARRAY VERSION OF M-HEAP

作者：Jung Haejae^*

来源：International Journal of Foundations of Computer Science, 2014, 25(1): 67-88.

DOI：10.1142/S012905411450004X

• Heap
• priority queue
• data structure
• performance

Both the post-order heap and the M-heap have a full binary tree structure and have constant amortized insertion and O(logn) deletion time complexities.
This paper proposes a simple array version of the M-heap, called AM-heap. The AM-heap has a complete binary tree structure and its array indexing scheme is the same as the simple indexing scheme of the conventional binary heap. An insertion on an AM-heap takes constant amortized time and a deletion takes O(logn) time where n is the number of elements in an AM-heap. The AM-heap resolves the open problem that is to design an array version of the M-heap. Also, it is simpler than the post-order heap to implement and debug.

• 出版日期2014-1