B-heap
A B-heap is a binary heap implemented to keep subtrees in a single page. This reduces the number of pages accessed by up to a factor of ten for big heaps when using virtual memory, compared with the traditional implementation.[1] The traditional mapping of elements to locations in an array puts almost every level in a different page.
There are other heap variants which are efficient in computers using virtual memory or caches, such as cache-oblivious algorithms, k-heaps,[2] and van Emde Boas layouts.[3]
See also
References
- ↑ Kamp, Poul-Henning (June 11, 2010). "You're Doing It Wrong". ACM Queue.
- ↑ Naor, Dalit; Martel, Charles U.; Matloff, Norman S. (1991). "Performance of Priority Queue Structures in a Virtual Memory Environment". Comput. J. 34 (5): 428–437. doi:10.1093/comjnl/34.5.428.
- ↑ van Emde Boas, P.; Kaas, R.; Zijlstra, E. (1976). "Design and implementation of an efficient priority queue". Mathematical Systems Theory. 10: 99–127. doi:10.1007/BF01683268.
External links
- Implementations at https://github.com/varnish/Varnish-Cache/blob/master/lib/libvarnish/binary_heap.c and http://phk.freebsd.dk/B-Heap/binheap.c
- Generic heap implementation with B-heap support.
- For more on van Emde Boas layouts see Benjamin Sach Descent into Cache-Oblivion or Cache-oblivious data structures.
This article is issued from Wikipedia - version of the 9/27/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.