earticle

논문검색

Performance Evaluation of Cache-aligned 4-ary AM-heap

초록

영어

AM-heap is a heap data structure with O(1) amortized insertion time and O(logn) deletion time complexities. This paper presents cache-aligned 4-ary AM-heap in which every node has four children except that the root has three children. In this heap, the leftmost node of each sibling has an index of a multiple of four. Also, every node index matches its corresponding array index and every sibling nodes smoothly fits into a single cache block. Our experimental results show that cache-aligned 4-ary AM-heap is faster than AM-heap as well as post-order heap.

목차

Abstract
 1. Introduction
 2. Related Works
 3. Cache-aligned 4-ary AM-heap
 4. Experimental Results
 5. Conclusion
 Acknowledgements
 References

저자정보

  • Haejae Jung Department of Information and Communication Engineering Andong National University, Andong, South Korea

참고문헌

자료제공 : 네이버학술정보

    함께 이용한 논문

      ※ 원문제공기관과의 협약기간이 종료되어 열람이 제한될 수 있습니다.

      0개의 논문이 장바구니에 담겼습니다.