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. The traditional mapping of elements to locations in an array puts (almost) every level in a different page.
- Implementations at http://www.varnish-cache.org/trac/browser/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 algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|